Minimum Unsatisfiable 3-CNF Formulae I am currently interested in obtaining (or constructing) and studying 3-CNF formulae which are unsatisfiable, and are of minimum size. That is, they must consist of as few clauses (m = 8 preferably) as possible, and as few distinct variables (n = 4 or more) as possible, such that removing at least one clause will render the formula satisfiable.

More formally, any qualifying 3-CNF formula F must satisfy the following conditions:

F is unsatisfiable
F has a minimum amount (4+) of distinct variables (or their negation)
F has a minimum amount of clauses (8+)
every proper subset of F is satisfiable (allowing removal of any arbitrary clause or clauses).
F has no 2 clauses that are reducible to a 2-CNF clause
e.g. (i, j, k) & (i, j, ~k) is NOT allowed ( they reduce to (i,j) )

For example, with n=4, there exists many minimal 8-clause 3-CNF formulae that are unsatisfiable. For one, by looking at the 4-hypercube and trying to cover it with edges (2-faces), one can construct the following unsatisfiable formula:

1. (~A,  B,  D)
2. (~B,  C,  D)
3. ( A, ~C   D)
4. ( A, ~B, ~D)
5. ( B, ~C, ~D)
6. (~A,  C, ~D)
7. ( A,  B,  C)
8. (~A, ~B, ~C)

This qualifies as a minimum unsatisfiable 3-CNF formula because:

It is unsatisfiable:

Clauses 1-3 are equivalent to:  D or A=B=C
Clauses 4-6 are equivalent to: ~D or A=B=C
They imply A=B=C, but by clauses 7 and 8, this is a contradiction.

There are only 4 distinct variables.
There are only 8 clauses.
Removing any clause renders it satisfiable.
No 2 clauses are 'reducible' to a 2-CNF clause.

So I guess my overall questions here are, in order of importance to me:

What are some other small minimum formulae which meet the above conditions?
(i.e. for say, 4,5,6 variables and 8,9,10 clauses)
Is there some sort of database or "atlas" of such minimum formulae?
What nonrandom algorithms exist for constructing them outright, if any?
What are some insights into these formulae's characteristics? Can they be counted or estimated, given n (# variables) and m (# clauses)?

Thank-you in advance for your replies.
I welcome any answer or comment.

Take the formula in your example, remove the clause $\lnot A \lor \lnot B \lor \lnot C$ and add the following $2$ clauses:

$\lnot A \lor \lnot B \lor \lnot E$
$\lnot B \lor \lnot C \lor E$

You will get a minimal unsatisfiable formula with $n=5$, $m=9$ obeying condition 5.

In general, you may randomly pick a clause $l_1 \lor l_2 \lor l_3$ and split it in $2$ clauses:

$l_1 \lor l_2 \lor v$
$l_2 \lor l_3 \lor \lnot v$

where $v$ is a new variable. Each time you do so, both $n$ and $m$ are incremented by $1$. Repeating this process allows you to "stretch" the initial unsatisfiable core, and to obtain minimal unsatisfiable formulas (obeying condition 5) whose $r=\frac{m}{n}$ tends to $1$ as $n$ grows (which is pretty rare, as formulas with $r=1$ are satisfiable with high probability).


How close can we get to linear multiply, add, and compare (on integers)? Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and comparision operations are computable in linear time:

  Does there exist a representation of integers so that addition, multiplication, and comparison are all doable in linear time? Basically, is there a linear time discretely ordered ring?

(1)  How close can we come to linear time multiplication and addition, without compares?  Here I assume that the problem sizes may vary, so that we may need a data structure/algorithm that allows for changing integer sizes.

(2)  For the complete problem, we can assume that we will find an optimum scheme for multiply, add, and compare on the integers.  How close can we get the slowest of these three operations (in the worst case) towards linear time?  And on that note, how fast would the other operations be?

FORMAL PROBLEM STATEMENT

As Emil Jeřábek mentions, we'd like to rule out trivial cases and concentrate on worst case behavior for this question.

So we ask, for non-negative integers $\forall x$ and $\forall y$ where $0 \le x < n$ and $0 \le y < n$, can we find a data structure/algorithm that can perform addition, multiplication, and compares with\between $x$ and $y$ in $O(n \log{(n)})$ time and $O(\log^2{(n)})$ space?

Probably not the best answer, but perhaps this is a useful starting point. If we wish to represent a non-negative integer, we can store it as a set of residues modulo sequential prime numbers starting from 2. In this form comparison is potentially hard, but multiplication and addition can be done pretty quickly. The product of the first $n$ primes is approximated by $$p_n\# =\exp((1+\mathcal{o}(1) )n\log n).$$
Hence to represent an integer $N$ you require residues modulo the first $n$ primes, where $N<\exp((1+\mathcal{o}(1) )n\log n)$. Since we can represent any $N<p_n\#$ using residues modulo the first $n$ prime residues, we can take $n \log n \propto \log(N)$. Addition and multiplication can be done directly between pairs of residues. There are $n$ such pairs, with the maximum prime being around $n\log(n)$. Thus addition should be in $O(n\log\log(N))$, while multiplication via Schonhage-Strassen should be in $O(n\log\log(N)\log\log\log\log(N)\log\log\log(N))$. Since $n \log n \propto \log N$, then a rough approximation gives $n$ in $O(\log N/\log\log N)$. This would give the complexity of addition and multiplication as approximately $O(\log N)$ and $O(\log N \log\log\log N \log\log\log\log N)$.


Finding balanced disjoint cycles in bridgeless cubic graphs Petersen's theorem states that a bridgeless cubic graph contains a perfect matching (1-factor). Motivated by this question, Complexity of finding 2 vertex-disjoint (|V|/2)-cycles in cubic graphs? I am interested in the problem of deciding the existence of perfect matching $M$ such that removing the edges of $M$ leaves two node-disjoint cycles of equal cardinality  (each cycle has size $|V|/2$).

  Is this problem solvable in P-time? Is it $NP$-complete?

The input is connected bridgeless cubic graph.

This is NP-complete; reduction from the question, "Does a 2-edge-connected cubic graph $H$ contain a Hamiltonian cycle avoiding a given edge $e$?"

Construct $G$ as follows.  Take two copies of $H-e$, denoting the endpoints of $e$ in the first copy $v_1$, $u_1$ and denoting the endpoints of $e$ in the second copy $v_2$, $u_2$.  Add edges $e_v$ between $v_1$ and $v_2$, and $e_u$ between $u_1$ and $u_2$.  Observe that $G$ is 2-edge-connected.

Any cycle of $G$ contains both or neither of $e_v$ and $e_u$, since these edges form an edge cut.  Thus if $G$ has two vertex-disjoint cycles of length $|V(H)|$, they must each lie in a separate copy of $H$.  Such cycles exist precisely if $H$ contains a Hamiltonian cycle avoiding $e$.

Edit: Am I missing something obvious, or is the question of finding a good perfect matching clearly equivalent to finding the two long cycles?


Dependent types over Church-encoded type in PTS/CoC I'm experimenting with pure type systems in Barendregt's lambda cube, specifically with the most powerfull one, the Calculus of Constructions. This system has sorts * and BOX. Just for the record, below I'm using the concrete syntax of the Morte tool https://github.com/Gabriel439/Haskell-Morte-Library which is close to the classical lambda calculus.

I see we can emulate inductive types by some kind of Church-like encoding (a.k.a. Boehm-Berarducci isomorphism for algebraic data types).
For a simple example I use type Bool = ∀(t : *) -> t -> t -> t with the constructors True = λ(t : *) -> λ(x : t) -> λ(y : t) -> x and False = λ(t : *) -> λ(x : t) -> λ(y : t) -> y.

I see that the type of term-level functions Bool -> T is isomorphic to pairs of type Product T T with classical Product = λ(A : *) -> λ(B : *) -> ∀(t : *) -> (A -> B -> t) -> t modulo parametricity by means of function if : Bool -> λ(t : *) -> t -> t -> t which is in fact identity.

All questions below will be about representations of dependent types Bool -> *.

I can split D : Bool -> * into pair of D True and D False. Are there the canonical way to create D again? I want to reproduce isomosphism Bool -> T = Product T T by an analogue of function if at type level but I cannot write this function as simple as original if because we cannot pass kinds in arguments like types.
I use a kind of an inductive type with two constuctors to solve question(1). The high level description (Agda-style) is the following type (used instead of type-level if)

data BoolDep (T : *) (F : *) : Bool -> * where
  DepTrue : T -> BoolDep T F True
  DepFalse : F -> BoolDep T F False

with the following encoding in PTS/CoC:

λ(T : *) -> λ(F : *) -> λ(bool : Bool ) ->
∀(P : Bool -> *) ->
∀(DepTrue : T -> P True ) ->
∀(DepFalse : F -> P False ) ->
P bool

Is my encoding above correct?
I can write down the constructors for BoolDep like this code for DepTrue : ∀(T : *) -> ∀(F : *) -> T -> BoolDep T F True:

λ(T : *) ->  λ(F : *) ->  λ(arg : T ) ->
λ(P : Bool -> *) ->
λ(DepTrue : T -> P True ) ->
λ(DepFalse : F -> P False ) ->
DepTrue arg

but I cannot write down the inverse function (or any function in the inverse direction). Is it possible? Or should I use another representation for BoolDep to produce an isomorphism BoolDep T F True = T?

You can't do this using the traditional Church encoding for Bool:

#Bool = ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool

... because you can't write a (useful) function of type:

#Bool → *

The reason why, as you noted, is that you can't pass in * as the first argument to #Bool, which in turn means that the True and False arguments may not be types.

There are at least three ways you can solve this:

Use the Calculus of Inductive Constructions.  Then you could generalize the type of #Bool to:

#Bool = ∀(n : Nat) → ∀(Bool : *ₙ) → ∀(True : Bool) → ∀(False : Bool) → Bool

... and then you would instantiate n to 1, which means you could pass in *₀ as the second argument, which would type-check because:

*₀ : *₁

... so then you could use #Bool to select between two types.
Add one more sort:

* : □ : △

Then you would define a separate #Bool₂ type like this:

#Bool₂ = ∀(Bool : □) → ∀(True : Bool) → ∀(False : Bool) → Bool

This is essentially a special case of the Calculus of Inductive constructions, but produces less reusable code since now we must maintain two separate definitions of #Bool, one for each sort that we wish to support.
Encode #Bool₂ directly within the Calculus of Constructions as:

#Bool₂ = ∀(True : *) → ∀(False : *) → *

If the goal is to use this directly within unmodified morte then only approach #3 will work.


Talk for K-12 Students + General Audience Reference Request I will be giving talks about general topics in CS, and want to hit on TCS as well. The talks will be given to K-12 schools, so not all of them will be seniors who may go to an undergraduate program at a university (Note: this question is different than Inspirational talk for final year high school pupils, which only concerns seniors).

I am looking for references/videos/lecture slides/etc. that deal with CS/TCS topics in a general perspective given towards high/middle/lower school students.

The only one I have been able to find so far is this one: https://www.youtube.com/watch?v=msp2y_Y5MLE by Michael Sipser on the P vs NP problem. It is interesting, but I want to know if there are other sources that give insight into major CS topics that they + a general audience may not have heard about before.

As one of the topics of your lecture, the problems from combinatorics might be good candidates.Generally, a high school student has some conception on permutation, combination and high school geometry. So, following examples illustrates what i mean.

Take arbitary points on plane. Can we always find a line such that the number of points above and below the line is same? If yes, how ?
Take a point set on plane. How can we find the minimum number of points that should be added to the point set such that it contains 4 points forming a square?

etc. Actually, the many problems in combinatorial geometry are even though hard to solve, but since they mainly focuses on points, lines they can act as motivational problems.


Is it considered OK to email authors to inquire about their paper while subreviewing their paper for a conference? More generally, how do you reconcile questions that you may have about the paper's technical material?

Usually any such ex-parte communication needs to go through the relevant PC. For example I was once on a PC where a subreviewer identified a bug in a paper they were reviewing for me. They relayed it to me, I discussed it with the other PC members assigned to the paper, and then we presented our conclusions to the PC chair who initiated contact with the authors.

This is for conferences without a rebuttal process (typically true for theory confs). If the conference has a rebuttal process then there's a formal mechanism for discussing this with the authors.

Finally, if you're not sure if there's a bug, then merely raise your doubt with the PC.

Update: a secondary issue that comes to mind after seeing Jeff's comment is a matter of fairness. Suppose ex-parte communications are not officially sanctioned, but are not frowned on. Then an author who happens to know people on the PC gets a slight advantage, because PC members might be more likely to contact the author. However, an official policy on how to handle such communication that does not depend on "knowing the author" implicitly or explicitly seems fairer.


Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets" I am looking for:

Michael O. Rabin, "Degree of difficulty of computing a function, and a partial ordering of recursive sets", Hebrew University, Jerusalem, 1960

Summary:

  “We attempt to measure the amount of work inherent in the task of computing a given computable (recursive) function. A notion of degree of difficulty of computing is introduced and studied. The notion is invariant in the sense that it is independent of the idealized computers (Turing Machines) used for computing the functions in question. Applications are made to the classification of solvable decision problems (recursive sets) according to relative difficulty.”

I couldn't find a copy online or at our library.

There are two loanable copies at The National Library of Israel.

Here is a scanned copy.


Theoretical computer science self-study resources for programmers I am a pretty proficient software engineer, but
I don't know much theory.
I want to learn more theory.
Particular topics that I am interested in are:
computational complexity, formal languages, and type theory.
But I am at a loss as for how to begin learning about these fields.

  What resources would you recommend to someone
  who wants to learn more theory through self-study?
  Are there any theoretical computer science self-study guides
  for software engineers?

There are several ways to learn about type theory. For a working programmer,
   Types and Programming Languages by B. Pierce is a good start.
Practical Foundations for Programming Languages by R. Harper might also be good. If you want a bit of easy to read background on operational semantics,
I recommend G. Winskel's, The Formal Semantics of Programming Languages: An Introduction. With T. Nipkow, G. Klein, Concrete Semantics, a variant of Winskel's book has been formalised for the Isabelle/HOL interactive proof assistant. I suspect it's really difficult to get to grips with a prover just from this (or any) book, you'd want an expert nearby to ask questions.
If you want a more mathematical approach to type-theory, you could look at
J. R. Hindley, J. P. Seldin, Lambda-Calculus and Combinators: An Introduction, or
H. Barendregt's, Lambda Calculi with Types. Although I wouldn't recommend starting from Barendregt.

If you want a single recommendation, I'd say read all of Pierce except Part VI (Higher-Order Systems), and implement the toy languages the book discusses. You'll end up with a strong grounding in type theory, and probably a better programmer too.


Is testing two SO-Horn queries for equivalence decidable? It follows from Rice's theorem that you cannot determine whether or not two Turing machines decide the same language.  My question is:  Does this also apply in descriptive complexity settings, particularly when it comes to testing a pair of SO-Horn queries to see if they describe the same language?  I'm not aware of any descriptive complexity version of Rice's theorem, and I could conceivably see that it might not be all that difficult to test two second-order formulas for equivalence.

First, note that the equality of two TMs is harder than the halting problem (it is $\Pi^0_2$-complete), i.e. you can not compute it even with an oracle for the halting problem. So it is not even c.e. (i.e. $\Sigma^0_1$, a.k.a. r.e.). Rice's theorem implies that the set is not c.e., it does not imply the stronger result.

There is a complexity theoretic version of Rice's theorem (by D. Kozen), but that gives a weaker result, which is expected, we can check non-trivial properties if we know that the machine halts, e.g. we can check if the machine accepts when run on an empty tape. Intuitively the result says (kind of) that the only way to check non-trivial properties of language of TMs is to simulate the machines (if I remember correctly).

Descriptive complexity does not change things, so I think you can ignore it and just replace it with the TMs with polynomial clocks (they can be converted to descriptive complexity characterization and descriptive complexity characterization can be converted to characterization using TMs).

I think the question of deciding the equality of even simpler functions is co-c.e.-complete (i.e. $\Pi_1$-complete). We can not check if two multinomials are equivalent over natural numbers (since the complement is c.e.-complete by the MRDP theorem), and this implies that we cannot check the equality of two SO-Horn queries.


Complexity class of this problem? I am trying to understand to which complexity class the following problem belongs:

Exponentiating Polynomial Root Problem (EPRP)

Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients drawn from a finite field $GF(q)$ with $q$ a prime number, and $r$ a primitive root for that field. Determine the solutions of:
$$p(x) = r^x $$
(or equivalently, the zeros of $p(x) - r^x$) where $r^x$ means exponentiating $r$.

Note that, when $\deg(p)=0$ (the polynomial is a constant), this problem reverts to the Discrete Logarithm Problem, which is believed to be NP-Intermediate, i.e. it is in NP but neither in P nor NP-complete.

To the best of my knowledge, efficient (polynomial) algorithms to solve this problem  do not exist (Berlekamp and Cantor–Zassenhaus algorithms require exponential time). Finding roots to such equation can be done in two ways:

Try all possible items $x$ in the field, and check whether they
satisfy the equation or not. Clearly, this requires exponential time in the bitsize of the field
modulus;
The exponential $r^x$ can be rewritten in polynomial form, by using
Lagrange interpolation to interpolate the points
$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$, determining a
polynomial $f(x)$. This polynomial is identical to $r^{x}$ precisely because we are working on a finite field. Then, the difference $p(x) - f(x)$, can be
factored in order to find the roots of the given equation (using
Berlekamp or Cantor–Zassenhaus algorithms) and the roots read off the factors. However, this approach is
even worse than exhaustive search: since, on average, a polynomial
passing by $n$ given points will have $n$ non-null coefficients, even
only the input to Lagrange interpolation will require exponential
space in the field bit size.

Does anyone know if this problem is believed to be NP-intermediate as well or belonging to any other complexity class ? A reference will be greatly appreciated. Thanks.

will take a stab at answering this. there are no refs given in the question but it is given an acronym "EPRP" as if more than one person has studied it. does anyone know if that is the case? the questioner MC seems to have significant bkg in this area but it would help significantly to list some "nearby" refs known/reviewed to understand why they have some gap that doesnt (?) cover this supposedly special case.

it usually helps to find "nearest available refs" and determine how the problem is different or similar. here is a comprehensive ref that seems to consider closely related problem(s). think that the questioner MC should try to locate the nearest case of the problem in this ref, or maybe some other one, and then point out how this case asked about is specifically different than general problem cases given in the ref. the ref has a long list of related refs to also check for nearby/related problem(s). he considers the complexity of the problem and gives efficient P-time algorithms for various cases.

ON SOLVING UNIVARIATE POLYNOMIAL
EQUATIONS OVER FINITE FIELDS
AND SOME RELATED PROBLEMS
Tsz Wo Sze, Doctor of Philosophy, 2007

  ...we present a deterministic polynomial-time algorithm to
  solve polynomial equations over some families of finite fields. Note that polynomial
  equations are powerful constructs. Many problems can be formulated as polynomial
  equations.


Is there a common mathematical symbology for collections? Preface: So, it was suggested in 'Programmers' that I ask this over here.

I am being asked to define several of my algorithms in mathematical terms to describe my work to a customer. I trying to determine if anybody knows whether common operators for collections like sequences, lists, tuples, etc have been defined. If so, is there a good reference that I could be pointed to. Thanks. I am interested in the actual symbols used. I am wondering if the following would make sense or be appropiate to anybody.

Given two sequences (or strings):

S = (A, B, C) and T = (A, D, H)

In my mind, the intersection of these sequences would look like S ∩ T = (A) and the union of these sequences would be S ∪ T = (A, B, C, A, D, H)

Specification languages such as Z have a vast range of data types and operations on them and, at least within that community, these are standardised. This tutorial gives a great overview. Other specification languages exist, such as B and Alloy which may also satisfy your requirements.


How to extend Solomonoff Induction to continuous domain Informally speaking, Solomonoff Induction provides an Bayesian optimal way to predict the next symbol from observed symbol sequences $S_1S_2S_3...S_n$ where each $S_i$ belongs to a finite symbol set $\Sigma$. To get the posterior probability distribution of the next symbol, we make a weighted average prediction of all Turing Machines that produces first $n$ symbols. For each Turing Machine $M$ within consideration, the weight would be inverse exponential of "complexity" of that Turing Machine.

$$p(M) = 2^{-L(M)}$$

Where $L(M)$ is the description length of $M$ in context of an universal Turing Machine $U$.

If we replace:

finite symbol set $\Sigma$ to continuous domain $D$, such as $R^n$.
Symbol sequence $S_i$ to discrete time series, for example $x_1x_2x_3...x_n$ where $x_i \in D$
Turing Machine $M$ to discrete time dynamical system, for example $x_{n+1} = f(x_n)$, which is mapping $R^n \to R^n$

The Bayesian inference would still work in this case, however we have to redefine the complexity measure $p(f) \to [0, \infty)$, which is probability density function of $f$.

Question: Is there any work or related theory that extends the complexity measure elegantly to dynamical systems?

I would also be interested in results for continuous dynamical systems, in terms of differential equations.

Thanks.

The set of computable real functions is also recursively enumerable. Assume it is enumerated by $(f_i)_{i\in\omega}$. Then the Solomonoff prior of $f_i$ is $p(f_i)=2^{-K(i)}$. So there is no difference whether the function is defined over natural numbers or real numbers, as long as it is computable.


Detecting/Locating endpoints of a bridge-like structure in images using Graph Theory I have asked similar questions on stackoverflow; as i couldn't post the very same question in this part of stackexchange.  However, i would still like to receive recommendations / advice from this side of stackexchange, so forgive me and correct me if this is not the right place to ask such question.

The image can be seen here!

Problem Scenario

I have a set of images that look like what you see on the left hand column as shown in the above picture.  What I am trying to detect/locate is actually the two endpoints that are shown on the right hand column in the above picture.  It's quite like locating the "two ends points" of the 'bridge'.

I sincerely would like to seek for your advice and recommendation to achieve such goals.  I have applied some basic morphological operations; however, either im doing it wrong or those basic morpological operations aren't working in this scenario.  (i have tried making it into skeletons; however, once the skeletons are formed, I can't seem to detect the cross with 3 edges).

Also, would Graph Theory be applicable in this case?  If so, how do i detect the end points using Graph Theory?

Thanks very much.

Edits

It looks like the original sets of images cannot be completely generalized like what i'd previously drawn.

i have attached the latest updates to this question. Below is a more detailed representation that includes the original segmented regions and the corresponding images that'd undergone a "thinning" morphological operation. Again, the left side is the originally segmented region; while on the right would be the points to be detected.

I extend my comment adding an image produced with an (old) piece of software I made to automatically fill a figure with a colored gel.

The steps are:

reduce colors to black and white (1 bit)
reduce DPI
remove noise
apply a standard thinning algorithm
remove edges shorter than a fixed amount (based on the whole figure size)

I was interested in finding the center of each zone; if you are interested in the exact length of the bridge you can use various techniques.

For example:

add a "growing" white circle at the two endpoints of the longest segment found and reapply the algorithm, until the graph becomes disconnected, or
scan the longest segment with an orthogonal line and calculate the length of its intersection with the original image;  cut the bridge when you find a fast change in the length of the intersection
...

EDIT

In order to transform the image into a graph, you must scan the 1bit bitmap produced with the thinning algorithm (the skeleton).

The algorithmm I used in my program, generates at most 3 neighbours (out of 8) for each pixel. So the graph construction can be done in this way:

1. start from top left pixel P=(x,y), create a starting node N_0=(x,y)
2. mark P as processed
3. count the unprocessed neighbours neig_num of P
   3.1 if neig_num = 0 then P is an endpoint of an edge
       - check if one of its neighbours is an already created node N
       - otherwise create a new node N=(x,y)
       - add an edge from N to the last node found LASTN
   3.2 if neig_num = 1 then P is an inner point of an edge, do nothing
   3.3 if neig_num = 2 then P is a node of degree 3
       - create a new node N=(x,y)
       - add an edge from N to the last node found LASTN
6. for each unprocessed neighbour P' of P recursively call 2 (passing P as LASTN).
7. stop when all pixels have been processed
8. do some clean up stuff: merge closer nodes, remove short edges,
   check if N_0 has degree 2 (we started on an edge in a closed path)


Applications of Complexity Theory Complexity theory seems to capture something fundamental about the
structure of the universe, in that it formalizes the intuitive notion
that some problems are harder than others.

Scott Aaronson predicted, "The NP Hardness Assumption will eventually be
seen as analogous to the Second Law of Thermodynamics or impossibility
of superluminal signaling."

So-called "hard problems" are the basis of modern cryptography.

Are there any other applications that utilize, depend on, or exemplify the
existence of computationally hard problems?

The most recent issue of the CACM has an article by Faliszewski, Hemaspaandra and Hemaspaandra on the use of complexity theory in the realm of social choice theory and election design in particular. One example of such a result is that while Arrow's theorem guarantees that any election system is 'hackable', it might be NP-hard to do so.


Context weakening as an explicit rule for languages of the the lambda cube? I'm trying to formalize the syntax and typing judgments of the Calculus of Constructions in Coq. I'm choosing to use the Pure Type Systems presentation of CoC; however, I've seen mild variations in the rules for PTS in different resources.
In Type Theory and Formal Proof: An Introduction, Nederpelt and Geuvers add context weakening as an explicit rule:
Γ ⊢ e : T
x \notin Γ
Γ ⊢ U : s
---------------------- t_weak
Γ, x : U ⊢ e : T

---------------------- t_var
Γ, x : T ⊢ x : T

Their formalization clearly requires t_weak, since t_var can only type the last variable in the context.
In ATAPL, Pierce instead chooses a more powerful rule for typing variables, and forgoes an explicit context weakening rule.
x : T \in Γ
----------- t_var'
Γ ⊢ x : T

Presumably, one would be able to derive a weakening rule from the rules Pierce chooses.
Are both these systems indeed equivalent? Is there any reason to choose one over the other for the sake of formalization in a proof assistant?

If you intend to formalize meta-theorems in a proof assistant, then it's probably better to avoid the general weakening rule because it will pollute all your inductive arguments. Every single induction on the derivation will contain the case "but what if the context got larger using weakening?" and that's going to be super annoying. I would recommend instead a sane variable rule and no weakening. You can always show that weaking is admissible.
As far as sane variable rules go, the one you quoted works well when variables are symbols and contexts are maps taking symbols to their types. If you indent to use de Bruijn indices, then you should use different variable rules (note that contexts are just lists of types because variable names are just natural numbers):
$$
\frac{ }{\Gamma, A \vdash \mathtt{var}_0 : A}
\qquad
\frac{\Gamma \vdash \mathtt{var}_k : B}{\Gamma, A \vdash \mathtt{var}_{\mathtt{succ}(k)} : B}$$


Can all unambiguous grammars be parsed in linear time? When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in $O(n^2)$ time, and I wondered if it is possible to do better:

  Can all unambiguous grammars be parsed in linear time?

I'm quite sure I read somewhere that this is the case, but it doesn't come up when searching the internet. The same question was asked here, but no answer was given as far as I know.

Unambiguous context-free parsing is in $O(n^2)$ using Earley's algorithm.  Whether there exists a parsing algorithm working in linear-time on all the unambiguous context-free grammars is an open problem.  One of the most advanced statements of this kind is due to Leo [1991], who showed that a variant of Earley parsing works in linear time for all LRR grammars.

[Leo 1991] Joop M. I. M. Leo.  A general context-free parsing algorithm running in linear time on every LR($k$) grammar without using lookahead, Theoretical Computer Science 82(1):165--176. doi: 10.1016/0304-3975(91)90180-A


Is there an oracle separating Parity-P from PSPACE? Is $ (\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?

From the comment above: you can use the same oracle $A$ used in:

Richard Beigel, Harry Buhrman, and Lance Fortnow. 1998. NP might not be as easy as detecting unique solutions. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC '98).

for which $P^A= \oplus P^A  \neq NP^A = EXP^A$  ($EXP^A=NP^A\subseteq PSPACE^A$ also holds)


Relation between hardness of recognition of a graph class and forbidden subgraph characterization I'm considering graph classes that can be characterized by forbidden subgraphs.

If a graph class has a finite set of forbidden subgraphs, then there is a trivial polynomial time recognition algorithm (one can just use brute force). But an infinite family of forbidden subgraphs does not imply hardness: there are some classes with infinite list of forbidden subgraphs such that the recognition can also be tested in polynomial time. Chordal and Perfect graphs are examples but, in those cases, there is a "nice" structure on the forbidden family.

Is there any know relation between the hardness of the recognition of a class and the "bad behavior" of the forbidden family? Such a relation should exist? This "bad behavior" has been formalized somewhere?

Although it seems intuitive that the list of forbidden (induced) subgraphs for a class $\mathscr{C}$ of graphs which has NP-hard recognition should possess some "intrinsic" complexity, I have recently found some striking negative evidence to this intuition in the literature.

Perhaps the simplest to describe is the following, taken from an article by B. Lévêque, D. Lin, F. Maffray and N. Trotignon.

Let $F$ be the family of graphs which are composed of a cycle of length at least four, plus three vertices: two adjacent to the same vertex $u$ of the cycle, and one adjacent to a vertex $v$ of the cycle, where $u$ and $v$ are not consecutive in the cycle (and no other edges).

Now let $F'$ be the family of graphs which are composed exactly the same way, except that you add four vertices: two adjacent to the same vertex $u$ of the cycle (as before), but now two adjacent to the same vertex $v$ of the cycle, where again $u$ and $v$ are not consecutive.

Then the class of graphs which has $F$ as the forbidden induced subgraphs has polynomial-time recognition, whereas the recognition of the class which has $F'$ as the forbidden induced subgraphs is NP-hard.

Therefore, I find it hard to conceive of any general condition that a list of forbidden induced subgraphs has to satisfy when it results in a class with (NP-) hard recognition, considering that such a condition will have to separate the "very similar" $F$ and $F'$ above.


Does BQP contain any NP-Complete problem? From the Wikipedia documentation, "the suspected relationship of BQP to other problem spaces" diagram suggests no intersection between NP-complete problems and BQP.

Has this been demonstrated or not?

To the best of my knowledge this is still open.


Maximal subcoalgebras of an $F+1$-coalgebra corresponding to an $F$-coalgebra This context of this question is Rutten's Universal Coalgebra, used for modelling systems.
I'm interested in finding a description of a functor between different types of coalgebras
corresponding to finding a certain subcoalgebra.

An $F+1$-coalgebra $\langle S, \alpha: S\to F(S)+1\rangle$ can be thought of as
a system whose transition shape is given by functor $F$ plus the possibility of an error/termination,
given by the $+1$. Assume that $F$ is a so-called Kripke polynomial functor: $F::=Id ~|~ B ~|~ F+F ~|~ F\times F ~|~ F^ A ~|~ \mathcal{P}_\omega F$, thus it preserves pullbacks.

A subcoalgebra of $\langle S, \alpha: S\to F(S)+1\rangle$ is coalgebra $\langle S', \alpha': S'\to F(S')+1\rangle$, where $S'\subseteq S$ and $\alpha'$ is $\alpha$ restricted to $S'$, such that its range falls withing $F(S')+1$.

I want to find the maximal subcoalgebra of this coalgebra which corresponds to an $F$-coalgebra. In terms of my application, this means I'm looking for the subset of states $S'\subseteq S$ that do not lead to the error state.

Clearly, I can take the pullback of the functions $\alpha: S\to F(S)+1$ and
$\mathit{inl}:F(S)\to F(S)+1$ to get a set $S_0\subseteq S$ which do not lead
to an error in the first step. Iterating this process for functors $F^i+1$ seems to lead to progressively smaller subsets $S_i$ of $S$ each avoiding the error state
for $i$ steps. What I'm lacking is a coherent description of the process.

Is whether there is a more universal description of this construction in terms of limits or colimits, or at least, some known approaches to the problem?

Suppose that the functor $F$ preserves monos. In fact, I am going to assume something slightly stronger, namely that $S \subseteq T$ implies $F(S) \subseteq F(T)$ (otherwise we have to insert isomorphisms here and there). Your Kripke functors are of this kind, I think.

First a little diversion. Let $G$ be a functor from sets to sets which preserves the subset relation. Consider a coalgebra $s : S \to G(S)$ and a subset $A \subseteq S$. Call a subset $T \subseteq S$ "good" if the restriction $s_T : T \to G(S)$ of $s$ to $T$ gives a coalgebra $s_T : T \to G(T)$ and the image $s(T)$ is disjoint from $A$. Any union of good subsets is again a good subset. Indeed, suppose $T_i$'s are good and let $T = \bigcup_i T_i$. Then $s$ restricted to $T$ maps into $\bigcup_i G(T_i) \subseteq G(T)$, and obviously $T$ is disjoint from $A$. Therefore, there exists the largest good subset of $T$, namely the union of all the good ones.

Now apply the previous paragraph to the functor $G(X) = F(X) + 1$ and $A = \lbrace \mathrm{inr}()\rbrace$ to get the desired result.


Computational power of a 2-PDA In our CS class, we have a question about the computational power of PDA's (Push Down Automaton).  A 0-PDA (PDA with no stacks) is equivalent to an NFA (Non-deteministic Finite Automaton), while a 1-PDA (the standard PDA) is equivalent to a CFG (Context Free Grammar).

However, a 2-PDA (PDA with 2 stacks) is more powerful (recognises more languages) than a 1-PDA, because it is not limited to pushing and popping on 1 stack only, but can also use the second stack.

The problem that I have is that I don't know how to prove the greater power of the 2-PDA.  My first thought was that a 2-PDA would be equivalent to a Turing Machine, but then I realised that it still wouldn't quite provide arbitrary access to the stack.

How would I go about proving that a 2-PDA is more powerful than a 1-PDA?

(Could someone with enough rep please tag this as homeworkpda - thanks)

First: Student's heuristics. At your level, what can you prove? Equivalence with TM or PDA should work by simulation. Equivalence to LBA might be slightly harder. Anything in between is certainly harder. So start with the easy inclusions.

You can see very quickly that languages like $a^nb^nc^n$ that are not context-free can be accepted by a 2-PDA. So you are certainly stronger than PDA.

Next in line is TM. Of course, every 2-PDA can be simulated by a 2-TM which can in turn be simulated by a TM. Turns out that the other direction works out, too. Take a TM and simulate it by a 2-PDA. You can keep the state graph but have to translate reading/writing/moving to reading$^2$/writing$^2$. What can simulate the TM's head? Also, take care what happens if the TM accesses new fields.

Can you figure it out now?


Is there a constant factor approximation algorithm for 2D rectangle coloring problem? The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the rectangles using minimum number of colors such that any two overlapping rectangles are assigned different colors.

This problem is known to be NP-hard. Xin Han, Kazuo Iwama, Rolf Klein and Andrezej Lingas (Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs) gave an O(log n) approximation. Is there a better approximation algorithm?

We know that the interval coloring problem is solved in polynomial time by first-fit algorithm by considering intervals according to their left endpoints. However, first-fit online algorithm is 8-competitive when the intervals appear in arbitrary order.

What is the performance of the first-fit algorithm for the rectangle coloring problem? What happens to first-fit algorithm when the rectangles appear according to their left (vertical) sides?

Thanks in advance for any help on this.

As suggested by the other answer, $\Omega(\log n)$ lower bound is not too hard to see. Let us do the sweeping bottom up with a horizontal line. The idea is to build components that require larger and larger number of colors. In particular, let $C(i)$ be a gadget that has a top rectangle with color $i$ (i.e., the first fit would assign it color $i$). Clearly, $C(1)$ is just a single rectangle.
The component $C(2)$ is

In general, the component $C(k)$ is a rectangle with $C(1), \ldots, C(k-1)$ hanging below it:

Now, it is easy to verify that a fit-first algorithm with sweeping  horizontally from the bottom would use $k$ colors to color $C(k)$. However, the intersection graph of $C(k)$ is just a tree, and it can be colored by $2$ colors. Now, $C(k)$ is just a Fibonacci tree in structure, and as such the number of nodes in it is $2^{O(k)}$, which implies $\Omega( \log n )$ gap.

Since there is a simple algorithm that gets $O( \log n)$ approximation to coloring of rectangles, this might be tight. I don't know.


Direct SAT to 3-SAT reduction Here the goal is to reduce an arbitrary SAT problem to 3-SAT in polynomial time using the fewest number of clauses and variables.   My question is motivated by curiosity.  Less formally, I would like to know: "What is the 'most natural' reduction from SAT to 3-SAT?"

Now the reduction that I've always seen in text books goes something like this:

First take your instance of SAT and apply the Cook-Levin theorem to reduce it to circuit SAT.
Then you finish the job by the standard reduction of circuit SAT to 3-SAT by replacing gates with clauses.

While this works, the resulting 3-SAT clauses end up looking almost nothing like the SAT clauses you started with, due to the initial application of the Cook-Levin theorem.

Can anyone see how to do the reduction more directly, skipping the intermediate circuit step and going directly to 3-SAT?  I would even be happy with a direct reduction in the special case of n-SAT.

(I would guess that there are some trade-offs between computation time and the size of the output.  Clearly a degenerate -- though fortunately inadmissible unless P=NP -- solution would be to just solve the SAT problem, then emit a trivial 3-SAT instance...)

EDIT:  Based on ratchet's answer it is clear now that the reduction to n-SAT is somewhat trivial (and that I really should have thought that one through a bit more carefully before posting).  I'm leaving this question open for a bit in case someone knows the answer to the more general situation, otherwise I will simply accept ratchet's answer.

Each SAT clause has 1, 2, 3 or more variables. The 3 variable clause can be copied with no issue

The 1 and 2 variable clauses {a1} and {a1,a2} can be expanded to {a1,a1,a1} and {a1,a2,a1} respectively.

The clause with more than 3 variables  {a1,a2,a3,a4,a5} can be expanded to {a1,a2,s1}{!s1,a3,s2}{!s2,a4,a5} with s1 and s2 new variables whose value will depend on which variable in the original clause is true


What is FO(REGULAR)? (The descriptive complexity equivalent of NC1) According to Immerman's Descriptive Complexity diagram, there is a logic called $\mathsf{FO(REGULAR)}$ which captures $\mathsf{NC}^1$. However, I can't find the reference where this logic is defined. Does anyone know the definition? And what paper originally proved this result?

Unlike the classes $\mathsf{AC}^i$ which are captured by iterated quantifiers ($\mathsf{FO}[\log^i(n)]$), it is interesting that $\mathsf{NC}^1$ would require extending the language with a new construct. I might imagine that it is some form of querying for membership in a regular language, but this is only a guess.

My copy of Descriptive Complexity (Immerman 1999) doesn't seem to mention the result (maybe I need the newer version). The best I can find is the paper

An algebra and a logic for NC1. Kevin J. Compton and Claude Laflamme, 1990.

which gives a logical characterization of $\mathsf{NC}^1$, but an apparently different one: it is called $\mathsf{FO} + \mathsf{RPR} + \mathsf{BIT}$ (first order logic extended with "relational primitive recursion" and the BIT relation, which gives binary representations of integers).

My interest in this is that I want a "natural" logic that extends both FOL and regular languages, and $\mathsf{NC}^1$ is the most immediate class to try. (Other possible choices are $\mathsf{L}$, $\mathsf{NL}$, and $\mathsf{NC}$, but these extensions would be less conservative.)

Professor Immerman kindly answered this by email:

  The definition of FO(REGULAR) is the set of all decision problems that are reducible to some regular language via first-order reductions.

Additionally, since the word problem for $S_5$ (which is a regular language) is complete for $\mathsf{NC}^1$ under FO reductions, this means that FO(REGULAR) can be defined equivalently as the set of decision problems that are reducible to $S_5$.

Other logics equivalent to $\mathsf{NC}^1$:

FO with monoidal quantifiers (Barrington, Immerman, Straubing, 1990: On uniformity within NC1)
FO with "relational primitive recursion" and the BIT relation (Compton, Laflamme, 1990: An algebra and a logic for NC1)
FO with width-5 transitive closure (Immerman, 1987: Expressibility as a Complexity Measure: Results and Directions)


Trees: complexity of counting the number of vertex covers Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?

The complement of a vertex cover is an independent set.  Your question is therefore equivalent to asking whether counting independent sets is #P-complete on trees.

The answer to this question is NO, it is not #P-complete: there is actually a polynomial-time algorithm to count the number of solutions.

S. D. Noble, Evaluating a Weighted Graph Polynomial for
Graphs of Bounded Tree-Width, The Electronic Journal of Combinatorics 16(1) R64, 2009. (link)

Noble actually shows much more.  Suppose the class of graphs under consideration has treewidth at most $k$.  Then the weighted graph polynomial $U$, which evaluated at a certain point yields the number of independent sets of a graph, can be evaluated in $O(a_k n^{2k+3})$ operations at any point.  Here $a_k$ depends only on $k$ and $n$ is the number of vertices in the input graph.  Hence there is a polynomial-time algorithm to count the number of vertex covers on trees (or any other class of graphs of bounded treewidth).

On the other side, it is interesting to ask: what is the smallest class that is known to be #P-complete?

  Theorem (Greenhill, 2000): counting independent sets in 3-regular graphs is #P-complete. (link).

In the comments Colin McQuillan pointed out an even stronger result:

Mingji Xia, Wenbo Zhao, #3-Regular Bipartite Planar Vertex Cover is #P-Complete, TAMC 2006, 356–364.

Note that wall graphs are 3-regular (if their corners are joined up), bipartite, and planar, but they have arbitrarily large treewidth.

Finally, a different graph polynomial $R_2$ yields the number of independent sets in a bipartite graph.  This was posed as an open question:

  Question (Ge and Štefankovič, 2010): is the exact evaluation of the $R_2$ polynomial easy for bounded tree-width graphs? (link)


Philosophy behind monotonicity requirement for inductive types Is there a good philosophical reason for why inductive types with negative occurrences or non-monotonicity should not be considered valid constructions?  According to my understanding of the Bishop/Martin-Löf view of mathematics, to construct a set is to say how to construct elements of said set (as well as say how elements are identified, but that's not so important for this discussion).  That's fine, but then I don't see why the standard inductive presentation of the naturals is a valid construction, but something like

Inductive bad :=
  | b : (bad -> bad) -> bad.

is not.  To be clear, I understand how such definitions yield inconsistencies and so I certainly understand from a purely pragmatic perspective why such restrictions need to be made.   However, it's one thing to be able to banish inconsistency, and another to be able to give a natural explanation for why such restrictions should be made.

When you write an inductive, you are defining a type by an equation. For example, if we write $F_1(X)=X^X=X\to X$, bad should satisfy $F_1($bad$)=$bad.

In general such equations can have several solutions, or none. For example, for $F_2(X)=X^X\times X$, you have (at least) two distinct solutions: $0$ (empty set) and $1$ (singleton). So you want some way to pick a specific solution.

The fact that you declared your type as inductive means that you pick the smallest solution (and coinductive would've meant the largest). So you want to be sure that this smallest solution exists. One way to ensure this is to ask for $F$ to be monotonous because then, the Knaster–Tarski theorem implies that it has a smallest fixpoint.

Aside from inconsistencies, I don't see a reason to ban other classes of equations, as long as you have a way to pick a specific solution. But unless you are sure that there is always a smallest solution for those equations, and that you will pick it, you probably shouldn't call it inductive.


Hierarchy for BPP vs derandomization In one sentence: would the existence of a hierarchy for $\mathsf{BPTIME}$ imply any derandomization results?

A related but vaguer question is: does the existence of a hierarchy for $\mathsf{BPTIME}$ imply any difficult lower bounds? Does the resolution of this problem hit against a known barrier in complexity theory?

My motivation for this question is to understand the relative difficulty (with respect to other major open problems in complexity theory) of showing a hierarchy for $\mathsf{BPTIME}$. I am assuming that everyone believes that such a hierarchy exists, but please correct me if you think otherwise.

Some background: $\mathsf{BPTIME}(f(n))$ contains those languages whose membership can be decided by a probabilistic Turning machine in time $f(n)$ with bounded probability of error. More precisely, a language $L \in \mathsf{BPTIME}(f(n))$ if there exists a probabilistic Turing machine $T$ such that for any $x \in L$ the machine $T$ runs in time $O(f(|x|))$ and accepts with probability at least $2/3$, and for any $x \not \in L$, $T$ runs in time $O(f(|x|))$ and rejects with probability at least $2/3$.

Unconditionally, it is open whether $\mathsf{BPTIME}(n^c) \subseteq \mathsf{BPTIME}(n)$ for all $c > 1$. Barak showed that there exists a strict hierarchy for $\mathsf{BPTIME}$ for machines with $O(\log n)$ advice. Fortnow and Santhanam improved this to 1 bit of advice. This leads me to think that a proving the existence of a probabilistic time hierarchy is not that far off. On the other hand, the result is still open and I cannot find any progress after 2004. References, as usual, can be found in the Zoo.

The relation to derandomization comes from Impagliazzo and Wigderson's results: they showed that under a plausible complexity assumption, $\mathsf{BPTIME}(n^d) \subseteq \mathsf{DTIME}(n^c)$ for any constant $d$ and some constant $c$. By the classical time-hierarchy theorems for deterministic time, this implies a time hierarchy for probabilistic time. I am asking the converse question: does a probabilistic hiearchy hit against a barrier related to proving derandomization results?

EDIT: I am accepting Ryan's answer as a more complete solution.

If anyone has observations about what stands between us and proving the existence of a hierarchy for probabilistic time, feel free to answer/comment. Of course, the obvious answer is that $\mathsf{BPTIME}$ has a semantic definition that defies classical techniques. I am interested in less obvious observations.

Let PTH be the hypothesis that there exists a probabilistic time hierarchy. Suppose the answer to your question is true, i.e., "PTH implies $BPP \subseteq TIME[2^{n^{c}}]$" for some fixed $c$. Then, $EXP \neq BPP$ would be unconditionally true. Consider two cases:

If PTH is false, then $EXP \neq BPP$. This is the contrapositive of what Lance noted.
If PTH is true, then "PTH implies $BPP \subseteq TIME[2^{n^{c}}]$" so again $EXP \neq BPP$.

In fact, even an infinitely-often derandomization of BPP under PTH would entail $EXP \neq BPP$ unconditionally. So whatever barriers apply to proving $EXP \neq BPP$, they apply to proving statements of the kind "PTH implies derandomization".


For a specific unbounded Turing machine, is its Halting problem undecidable? The question is on the title.

To make it clearer, I state some facts. We all know that the Halting problem with  input is undecidable. It leads to, given a specific input (e.g. empty string), the corresponding Halting problem with  input is also undecidable. Moreover, given a time or space bounded Turing machine M, the Halting problem of that specific M is decidable (on input x, save all of the configurations of M on x to check if M loops on x).

From there, I naturally have this question. I believe the problem is undecidable (because, otherwise, there seems to be no way to compute if M loops or not). But I haven't proved it yet.

It depends in which sense you mean "undecidable".

If you evaluate $M$ on the empty input, and want only to find a yes/no answer, then the algorithmic problem is trivially decidable, as answered by Gamow, since either the algorithm outputting "Yes", or the one outputting "No" is correct. you don't have to know which one is correct to prove decidability: there exists an algorithm solving the problem.

If your Halting problem on a specific $M$ still accepts the input $x$ of the machine as input of the problem, then it is in general undecidable. This is because it is equivalent to the general Halting problem by using a universal Turing machine $M_{univ}$, and giving as input the encoding of the Turing machine you want to test.
For simpler machines, of course, this problem can become decidable.

But coming back to the first version with no input, interestingly, there are Turing Machines for which the answer is actually mathematically undecidable. This means that the machine does not halt, but you cannot prove it using your usual mathematical theory (say ZFC for instance). To see this, consider a machine looking for a proof of contradiction in ZFC, and halting when it finds one. If ZFC is not contradicatory, the machine won't halt. But by Gödel's second incompleteness theorem, you cannot prove that this machine won't halt, since this would amount to prove there is no proof of contradiction in ZFC.

Remark that if the machine halts, then it is always possible to prove it, by exhibiting the full run of the machine.

So in my opinion, the answer to your question is: "the Halting problem can be undecidable for a specific Turing machine, even with no input", but we have to be precise about the meaning of "undecidable" here: it is in the sense of mathematical undecidability, i.e. independent of the axioms.


Set cover in which some pairs of sets are forbidden I'm trying to find an approximation algorithm for a variant of the weighted set cover problem.  However, this variation doesn't seem to let me apply the traditional set cover arguments for an approximation.  I'd like to know if anyone has ever encountered a similar problem (and, if possible, have info on the approximability of the problem - I'd be glad to have a factor $f$ approximation as there is for set cover, $f$ being the maximum frequency of some element $u \in U$).

Say we're given a ground set $U$, subsets $\mathcal{S} \subseteq U$, $\overline{\mathcal{S}} \subseteq U$ and a forbidden set of pairs of the form $\{S, \overline{S} \}$ with $S \in \mathcal{S}, \overline{S} \in \overline{\mathcal{S}}$.

We can assume that every set is in exactly one forbidden pair, i.e. there is a bijection between $\mathcal{S}$ and $\overline{\mathcal{S}}$ that forms the forbidden pairs.  We can also assume that $\cup_{S \in \mathcal{S}}S = \cup_{\overline{S} \in \overline{\mathcal{S}}}\overline{S} = U$, to guarantee the existence of a set cover without forbidden pairs.

Each set is also weighted by some weight function $w : \mathcal{S} \cup \overline{\mathcal{S}} \rightarrow \mathbb{R}$.

I want to find a set cover of minimum weight in which no forbidden pair is present.  That is, find $S_1, \ldots, S_k \in \mathcal{S} \cup \overline{\mathcal{S}}$ of minimum total weight such that $\cup_{1 \leq i \leq k}S_i = U$ such that for any $i, j$, $\{S_i, S_j\}$ doesn't form a forbidden pair.

This problem is way harder than set cover. Here is why...

Intuitively, you can encode independent set as a problem of this type. Indeed, you are given an instance of independent set - a graph $G$ with $n$ vertices, and a number $k$, and the question is whether the graph $G$ has an independent set of size $k$.

We assume that $k$ is large (say, polynomial in $n$).

It is not hard to form a set system, with $n$ sets, such that any cover of the set system requires at least $\Omega(k/\log n)$ sets, and any specific set of $k$ sets cover the ground set. To this end, have a "large" ground set $X$ (say, of size $t$), and generate $n$ random sets (independently), where you pick every element $x \in X$ to be in the $i$th random set with probability roughly $p = 10(\ln n)/k$. Let $R_1, \ldots, R_n$ be the resulting random sets, and observe that a union of any specific $k$ of them covers the ground set, with high probability. Indeed, the probability that an element of $X$ is not covered, by a specific $k$ sets is bounded by
$$
t (1-p)^k < 1/10,
$$
for $t = n^{O(1)}$.

Similarly, consider $k' = c (k/\log n)$ random sets, where $c$ is a sufficiently small constant. We claim that with high probability their union does not cover $X$. Indeed, the probability a specific element is covered by such $k'$ sets is
$1- (1-p)^{k'}$ which is a constant, say $\alpha < 1$. As such, the probability that these $k'$ random sets cover $X$ is at most $\alpha^t$. In particular, the probability that any of the possible sets of $k'$ random sets cover $X$ is bounded by
$$
\alpha^t * \binom{n}{k'} < 1/10,
$$
by taking $t$ to be larger than $20 (k/\alpha) \ln n$ (or some similar quantity).

Now, associate with the $v_i$ vertex in $G$, the set $R_i$. Forbid the pair $\{R_i, R_j\}$ if the edge $v_iv_j$ is in the graph $G$.

Any solution for the resulting instance, would be an independent set in $G$ of size $\Omega(k / \log n)$. The original independent set of size $k$ is a valid solution in the resulting instance (all with good probabilities). But that implies that using your problem, you can get a log approximation to independent set, which is an extremely unlikely event. More generally, a $\beta$ approximation, would imply a $O( \beta \log n)$ approximation for independent set. Since independent set can not be approximated to within $n^{1-\epsilon}$, you essentially get the same result for your problem.

PCP people might be able to derive the above from their known machinery...


Dependent Types and Compile Time Types I am trying to grok dependent types, and there's something that I find unclear.

In C++, templates can have non-type (template) parameters. The values of these parameters have to be specified at compile time, and it is then - at compile time - that the value-dependant types are defined/created/generated/declared.
It is not possible to generate a dependent-type with a run-time value.

Beyond syntactic differences, how are languages with dependent types like e.g. Idris different from what C++ does (albeit with somewhat awkward and possibly convoluted syntax)? After all, the whole point of their strong type systems is also to catch type errors at compile time, so obviously any runtime behavior is already after all the compile time checks have succeeded.

If I was to define the proverbial fixed-size list/vector type (where the list size is embedded in the type), then append() would return a (new) list of a new type with the new incremented size specified as part of the type. In C++, you would need to know the actual types, i.e. the size of the list, at compile time. There is no way to call append() on the result of the previous append() call, a runtime-determined number of times (as in a loop), because there is no (obvious) way to specify the type of the object to hold the previous result at runtime. Calling it recursively would cause a compile-time stack explosion.

What does e.g. Idris do that is different?
What extra power comes from dependent-types in languages that support them?
Alternatively, what is C++ missing to be considered as a language that supports dependent-types?

A language can be thought of as having both a static semantics, which determines the compile-time analysis that occurs; and a dynamic semantics, which determines the execution-time behavior of programs.

In Standard ML, for example, the static semantics concerns a language of Modules and a language of Types. The semantics show how types are assigned to terms in the core language and then checked for consistency. The module static semantics describe how signatures and structures are matched, how functors transform one structure to another, etc.

This is a fairly rich and complex language that is evaluated solely at compile-time; once this occurs, almost all of the semantic objects involved are no longer relevant to the execution semantics of the program and can be forgotten. The semantics works over the same syntax as the dynamic semantics, but the static semantics is very different in character from the dynamic semantics!

In a language such as Idris, which is dependently typed, the character of evaluation of the static semantics and the dynamic semantics ends up having far greater overlap. Instead of the static semantics working over types and the dynamic semantics working over values, both semantics now encompass both types and values. This doesn't mean that there aren't differences in the character of the static and dynamic semantics, just that there is significant overlap and they both concern some of the same semantic objects. In particular, the static semantics is often restricted to total functions, which ensures that evaluation will terminate (albeit sometimes after a lengthy delay).

Some parts of programs in dependently-typed languages exist only to provide evidence in the static semantics that other parts of the program are indeed well-typed. Idris doesn't make any syntactic distinctions here, but ATS (a systems programming language with dynamic semantics similar to C, but with a dependent type system) syntactically distinguishes terms that exist only to provide proof of assertions made in types. Idris does, on the other hand, allow annotation of programmer intent that some terms be "erased", which will produce an error in the static semantics if that desire can't be met.

Now, with that out of the way, let's look at C++ templates:

Instead of dealing with polymorphism and dependency of types on values directly in the static semantics, C++ adds an extra untyped language of template expansion into the static semantics. Rather than deal with complex static semantics, extra code is generated that should be checkable simply via the simple core language static semantics.

Although this lets you deal with some of the same practical problems that can be solved with polymorphic and more general dependent types (polymorphism is just a different sort of dependency, one of terms depending on types) it's not actually part of the type system; it's just an extra layer in the static semantics separate from the type system. Furthermore, the only way any extra "stuff" generated by template expansion could be erased would be by the general "dead code elimination" portion of the compiler, which isn't even a well-defined part of the static C++ semantics.

Sometimes in a dependently-typed language, type parameters can't be erased at run-time, because they are relevant to the determination of the run-time semantics. In C++, you would have to carry an extra parameter as well; this might be a "length" parameter that would be part of a Vector type in a dependently-typed language. C++ lacks the ability to make such parameters implicit and to define code that automatically calculates on them and make appropriate consistency checks with them.

Dependently-typed languages give you the choice of how much effort you will put into static proof of the runtime-irrelevance of such parameters; with little effort you can let them carry over into the dynamic semantics and be run-time checked, but with more effort you may be able to supply a proof that the property asserted by the type term is never violated and thus erase the run-time representation entirely.


SAT formula specifying that exactly $k$ of $N$ boolean variables are active using less than $N$-choose-$k$ terms Is there a way to express the condition that exactly $k$ of $N$ boolean variables are active without writing a disjunction of $N$-choose-$k$ terms, i.e., all possible configurations of the $N$ variables where exactly $k$ are active? Is the same true for specifying that at least $K$ of the $N$ boolean variables are active?

I'm aware that this is a problem dealt with in theoretical computer science but I couldn't find any references.

There are many ways.  See Encoding 1-out-of-n constraint for SAT solvers for a compendium of several ways and for a useful reference with more information.

From a practical perspective, the different schemes have different tradeoffs.  If you are trying to encode a $k$-out-of-$N$ constraint in something you are feeding to a SAT solver, you can try each of the different candidate encodings to see which makes the SAT solver run faster; they can have a significant impact on the efficiency of the SAT solver.


What can I say about the Parikh map of a CSL? Write $\Psi$ as the Parikh map--i.e., $\Psi(w) = \{(\#_\sigma(w))_{\sigma\in \Sigma}\vert w\in L\}$, where $\#_\sigma(w)$ is the number of times $\sigma$ appears in $w$. It's well-known that, for a CFL $L$, $\Psi(L)$ is a semilinear set (this is Parikh's theorem). Some other interesting things are known, but I have found nothing about the Parikh map of a context-sensitive language. In particular,

  what can I say about $\Psi(L_2 - L_1)$
  or $\Psi(\bar{L}_1)$ if $L_1, L_2$ are
  context-free? For instance, if I let
  $\phi(L) = \{\sum_\sigma \#_\sigma(w)\vert w\in L\} = \{|w|
 \vert w\in L\}$, is it possible that
  there is a CFL $L$ such that
  $\phi(\bar{L}) = \{n!\vert n\in
 \mathbb{N}\}$? (or any other
  'increasing' sequence converging in
  $\hat{\mathbb{Z}}$, for that matter.)

Regarding the second part of your question: If you choose your CFL $L$ to be the set of all invalid computations of a Turing machine $M$ (see, e.g., Chapter 8.6 in the first edition of "Introduction to Automata Theory, Languages, and Computation"), $\phi(\overline{L})$ is the set of all lengths of encodings of accepting computations of $M$.

Although this does not directly answer your question, you can use this approach to construct quite complicated sets.


Borel-Cantelli Lemma and Derandomization I was reading a paper titled Random Oracles with(out) Programmability. The last paragraph of section 2.3 reads:

  [Using our novel approach] there is no
  need to apply well-known classical asymptotic (and uniform) derandomization
  techniques based on the Borel-Cantelli lemma. To the best of our knowledge,
  this approach is novel to this paper.

I took a look at Wikipedia's entry for Borel–Cantelli lemma, and almost grasped the idea. However, I couldn't still figure out how it relates to derandomization. In addition, I don't understand the meaning of "asymptotic" and "uniform" in the aforementioned paragraph.

PS: Googling for Borel-Cantelli and derandomization will show several interesting results, but I don't have enough background to understand them well.

I don't think they mean derandomization in the traditional sense.  Try looking at the application of the BC lemma in this paper for an example of what they are talking about: http://www.cs.bu.edu/~reyzin/hash.html.

They say "asymptotic" because most BB separations apply to concepts like one-way functions, which are defined asymptotically.  Their result is instead a "concrete" bound that applies to all values of the security parameters, not just sufficiently large values.


Which 2P1R Games are Potentially Sharp? Two-prover one-round (2P1R) games are an essential tool for hardness of approximation.  Specifically, the parallel repetition of two-prover one-round games gives a way to increase the size of a gap in the decision version of an approximation problem.  See Ran Raz's survey talk at CCC 2010 for an overview of the subject.

The parallel repetition of a game has the astonishing property that while a randomized verifier operates independently, the two players can play the games in a non-independent way to achieve better success than playing each game independently.  The amount of success is bounded above by the parallel repetition theorem of Raz:

  Theorem: There exists a universal
  constant $c$ so that for every 2P1R
  game $G$ with value $1-\epsilon$ and
  answer size $s$, the value of the
  parallel repetition game $G^n$ is at
  most $(1-\epsilon^c)^{\Omega(n/s)}$.

Here is an outline on the work of identifying this constant $c$:

Raz's original paper proves $c \leq 32$.
Holenstein improved this to $c \leq 3$.
Rao showed that $c' \leq 2$ suffices (and the dependence on $s$ is removed) for the special case of projection games.
Raz gave a strategy for the odd-cycle game that showed Rao's result is sharp for projection games.

By this body of work, we know $2 \leq c\leq 3$.  My two questions are as follows:

  Question 1: Do experts in this area
  have a consensus for the exact value
  of $c$?

If it is thought that $c > 2$, are there specific games which are not projective, but also specifically violate the extra properties of projection games that Rao's proof requires.

  Question 2: If $c > 2$, which
  interesting games violate Rao's
  strategy and have a potential to be
  sharp examples?

From my own reading, it seems the most important property of projection games that Rao uses is that a good strategy for parallel repetition would not use many of the possible answers for certain questions.  This is somehow related to the locality of projection games.

I tend to believe that c=3 is the right answer for the general case, and that it should be possible to give an example. I'll have to think more about that to know for sure.
It's a good question, and I don't know of existing work about it.

Research recently focused on which types of games have (best possible) c=1, mostly because of possible applications to amplification of unique games.

Barak et al generalized the counterexample of Raz to all unique games with SDP gaps.
Raz and Rosen showed that for expanding projection games c=1. There are also previous results by a super-set of those authors for free games.


What are some real world applications for genetic algorithms? What are some real world problems that have been solved using a genetic algorithm?   What is the problem?  What is the fitness test used to solve this problem?

The optimizer in relational databases. Examples are PostgreSQL and H2; other databases most likely also use a genetic algorithm. The problem is: selecting the best query plan (the one with the lowest estimated cost) is NP-hard. The fitness test is the estimated cost.


Making a minimum-width tree decomposition lean in polynomial time As is well known, a tree decomposition of a graph $G$ consists of a tree $T$ with an associated bag $T_v \subseteq V(G)$ for each vertex $v \in V(T)$, which satisfies the following conditions:

Every vertex of $G$ occurs in some bag of $T$.
For every edge of $G$ there is a bag containing both endpoints of the edge.
For every vertex $v \in V(G)$, the bags containing $v$ induce a connected subtree of $T$.

We may also demand the following condition, called leanness, from our decomposition:

For every pair of bags $T_a$, $T_b$ of $T$, if $A \subseteq T_a$ and $B \subseteq T_b$ with $|A| = |B| = k$, then either a) there are $k$ vertex-disjoint $A-B$ paths in $G$, or b) the tree $T$ contains an edge $pq$ on the path from node $a$ to node $b$ such that $|V(T_p) \cap V(T_q)| \leq k$ and the set $V(T_p) \cap V(T_q)$ intersects all $A-B$ paths in $G$.

Robin Thomas showed that there is always a minimum-width tree decomposition which is also lean, and simpler proofs of this fact have been provided by several authors, for example by Patrick Bellenbaum & Reinhard Diestel.

  What I am interested in is the following: given a graph $G$ and a
  minimum-width tree decomposition of $G$, can we find a minimum-width
  lean tree decomposition of $G$ in polynomial time?

The two mentioned proofs do not yield such efficient constructiveness. In the paper of Bellenbaum and Diestel it is mentioned that "Another (more constructive) short proof of Thomas’s theorem has been given in P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universitat Hamburg 2000." Alas, I have not been able to find the manuscript online and my German is not that great.

Here is a formal reason why the problem is not poly-time solvable unless P=NP. We know that finding the treewidth of a given graph is NP-Hard. Given a graph $G$ we can add a disjoint clique of size $V(G)+1$ to create a new graph $G'$. A min-width tree-decomposition of $G'$ can be obtained as follows: it has two nodes with one bag containing all the nodes of the clique and the other containing all the nodes of $G$. Now making this tree-decomposition lean would require finding a lean-tree decomposition of the original graph $G$ which would, as a by-product, give the treewidth of $G$.


Far point queries in high dimensions Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$".

This is the dual of the "near neighbour" problem studied by people like Andone and Indyk. I'm wondering if it has a name in the literature. Certainly "far neighbour" doesn't make much sense.

There are a few references on "farthest point queries", however nothing recent and nothing that works in high dimensions.

Are you aware of a name for the described problem in newer literature?

See the following paper. The two problems are equivalent more or less. To see that, assume that the points are on the unit sphere centered at the origin, and observe that if your NN query $q$ is on the sphere, then the far neighbour for the antipodal point $-q$ is the NN to $q$. There might be a full version written somewhere on the web...

http://dblp.org/rec/conf/soda/GoelIV01

Yep, here is a postscript of the full version:

http://web.stanford.edu/~ashishg/papers/reductions.ps

(Postscript is a file format used in the 20th century to ensure that future generations would not be able to read the content of the file.)


Generate a sequence of numbers I want to generate an infinite sequence of numbers between $0$ and $9$ such that the percentage of number $i$ appearing in the sequence is $p_i$. Let $p=\lbrace p_0,...,p_9\rbrace$.

Another agent $B$ will observe $k$ consecutive elements from the sequence. Then it will update its belief about the probability of $p_i$ using a belief update rule (let's say a simple frequentist, i.e., the number of occurrences of each digit divided by $k$).

The question is how can I generate the sequence such that $B$'s belief $q$ is close to $p$, i.e., $d(p,q)$ is minimized where $d(p,q)$ is the dsitance function of two distributions, e.g., $d(p,q)=(\sum_i (p_i-q_i)^2)^0.5$.

Note that I don't know how $B$ will choose the $k$ numbers. Let's consider the worst case (i.e., worst $p'$).

For observing consecutive elements: pick up the best sequence of $k$ elements (depending on your proximity measure), and repeat it. Then B will always observe the same sequence (I assume that cyclical permutation doesn't affect B).

For observing random elements: how would you pick them randomly? Do you want a deterministic sequence?


Number of different longest common substrings Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The longest common substring problem asks for a longest string in the set $A(w_1,w_2)$ of all common substrings of $w_1,w_2$. We can define $A(w_1,w_2)$ as follows:
$$A(w_1,w_2)=\{s\in\Sigma^*\mid w_1=x_1sx_2,\;w_2=y_1sy_2,\;x_1,x_2,y_1,y_2\in\Sigma^*\}$$
In genereal, this substring $s$ is not unique. Therefore, I am looking for the maximal number $m(k,n)$ of different longest common substrings for an arbitrary pair of strings of length $n$. Formally:
$$m(k,n)=\max\limits_{w_1,w_2\in\Sigma^n}\left|\left\{s\in A(w_1,w_2)\mid\forall x\in A(w_1,x_2):\;|s|\ge |x| \right\}\right|$$

Natural upper bound: It is easy to see, that $m(k,n)\le n$ since the maximal number of substrings of the same length for a strings of length $n$ is $n$ (for substrings of length $1$). For $n\le k$ we even achieve $m(k,n)=n$ (take a string $w_1$ which consists of different letters and $w_2$ the reverse string of $w_1$). For $n> k$ we conclude that $m(k,n)<n$, but from now on it seems to be difficult.

Lower bound: Based on De-Bruijn sequences it is possible to deduce a lower bound as follows:
As a conclusion of a paper of  Lin et al, for each $m$ there are orthogonal De-Bruijn sequences $B_1(k,m)$ and $B_2(k,m)$ of length $k^m$, which means that the longest substring of $B_1(k,m)$ and $B_2(k,m)$ is of length $m$. The special property of (those) De-Bruijn sequences is, that each string of length $m$ is actually a substring (some of them by reading the De-Bruijn sequence cyclic). Therefore, both $B_1(k,m)$ and $B_2(k,m)$ containing $k^m-m+1$ different subtrings of length $m$ (acyclic) and for that reason there are at least $k^m-2m+2$ different longest common substrings for $B_1(k,m)$ and $B_2(k,m)$. So, for $n$ as a power of $k$, we get
$$m(k,n)\ge n-2\log_kn+2$$
I'm quite sure we can achieve a very close result (caused by some rounding-issues) for each $n$.

But my question is, how tight are these bounds? I could imagine that orthogonal De-Bruijn sequences are already (asymptotic) worst case examples, i.e.
$$m(k,n)\in n-\Theta(\log n).$$
But I am neither sure about this nor able to show it.

Any help is welcome!

Let $\ell$ be the length of the longest common substring. The number of longest common substrings $m$ is at most
$$ m \leq \min(k^\ell,n-\ell+1). $$
Let $x = \log_k n$. If $\ell \leq x-1$ then $m \leq n/k$. Otherwise, $m \leq n-\log_k n+2$. One checks that the latter bound is always worse, and so $m \leq n-\log_k n+2$.


Optimization Problem on a Directed Graph I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For each node we can compute the "activation value" $a_i$ as a sum of the activation values of the selected predecessor nodes, i.e.:
$$a_i = \sum_{j \in P(i)}x_{ji}a_{j}$$
where $x_{ij} \in \{0,1\}$ are edge selector variables and $P(i)$ is the set of predecessor nodes of $i$. The optimization objective is for each node in the graph to select a set of incoming edges with minimal cost that "activate" that node:

$$\underset{x}{\text{argmin  }}\sum_{i} \sum_{j \in P(i)} a_ix_{ji}$$
$$\text{  such that  }  \sum_{j \in P(i)}x_{ji}a_{j}\ge v_i, \forall{i}$$

We can assume that there exist some leaf nodes in the graph whose activation value is 1, and that each node in the graph can be activated for a large enough subset of incoming edges.

If $G$ is a DAG, then we can solve this with dynamic programming, but I can't seem to figure out if there is a way to do this on a general DG, or if its NP hard.

Any pointers are appreciated. Thanks a lot.

lemma 1. The posted problem (as I understand it) is NP-hard, even on DAGs,

Proof. The proof is by reduction from Subset Sum.  Given a Subset Sum instance with $n$ positive integers $x_1, x_2, \ldots, x_n$ and target $T$, the reduction produces the following instance of your problem.  The instance will have a minimal solution (one with objective equal to the sum of the activation values -- the minimum possible) if and only if some subset of the $x_i$'s sums to $T$.

Let the $x_i$'s be $b$-bit integers for some $b$, so the input instance has size polynomial in $n$ and $b$ and each $x_i$ is an integer in $\{1,2,\ldots, 2^b\}$.

Construct a "tower" gadget with two leaves $u_0, w_0$ with activation 1.  For each $i\in\{1,2,\ldots, b\}$, add two vertices $u_i, w_i$ each with activation threshold $2^i$ and two incoming edges: $(u_{i-1}, u_i)$, $(u_{i-1}, w_{i})$, $(w_{i-1}, u_i)$, $(w_{i-1}, w_i)$.  In any feasible solution to the instance (so far), each such vertex $u_i$ and $w_i$ will have to use both its incoming edges, and will have incoming activation value exactly equal to its activation threshold $2^i$.

Next, for each integer $x_i$ in the given Subset Sum instance, construct a vertex $X_i$ with activation threshold $x_i$, with edges from every $u_j$.  In any minimal solution, each $X_i$ will use just those incoming edges that represent the binary representation of $x_i$, thereby achieving incoming activation value equal to $x_i$ (and this is always possible).

Finally, construct a "root" vertex $R$ with activation value $T$ (the Subset Sum target) and edges from every vertex $X_i$.  There will be a subset of edges into $R$ to use to achieve activation value $T$ if and only if there is a subset of the $x_i$'s that sums to $T$.  $~~~\Box$

What am I missing?  As I understand the problem, showing NP-hardness seems like a nice homework exercise...

Given that Graphman was last active in 2016, perhaps clarification is not to be had.


Complexity of digraph homomorphism to an oriented cycle Given a fixed directed graph (digraph) $D$, the $D$-COLORING decision problem asks whether an input digraph $G$ has a homomorphism to $D$. (A homomorphism of $G$ to $D$ is a mapping $f$ of $V(G)$ to $V(D)$ that preserves the arcs, that is, if $uv$ is an arc of $G$, then $f(u)f(v)$ is an arc of $D$.)

The class of $D$-COLORING problems is strongly connected to the Dichotomy Conjecture for CSPs stated by Feder and Vardi (accessible on citeseer).

In this 2001 paper (accessible on the author's page, here), Feder proves a dichotomy theorem when $D$ is an oriented cycle (by oriented cycle I mean an undirected cycle where each edge is replaced by a single arc, that can be oriented arbitrarily), in other words, he shows that for any oriented cycle $D$, $D$-COLORING is either polynomial-time solvable or NP-complete.

Unfortunately, Feder's classification is highly nontrivial and not explicit, as the complexity of many cases is related to the complexity of certain restricted variants of SAT that depend on the orientation. By looking at the paper, I have not been able to determine the answer to my question:

  Question: What is the smallest size of an oriented cycle $D$ such that $D$-COLORING is NP-complete?

The answer might be stated somewhere in the literature, but I could not find it.

Edit: Let me give more details on Feder's classification. Feder shows that any NP-complete oriented cycle must be balanced, that is, have the same number of arcs in both directions (hence it has even order). Then, consider the "levels" induced by the orientation (start to go around the cycle at an arbitrary vertex; if an arc goes right, you go up by 1, if an arc goes left, you go down by 1). Then, if there is at most one "top-bottom run", it is polynomial. If there are at least 3 such "runs" and the cycle is a core, it is NP-complete. (In András' example from the comments, there are three such "runs", but the cycle is not a core.) The most tricky cases are those with two "top-bottom runs". Some are hard, some polynomial, and Feder relates them to special SAT problems to obtain a dichotomy. I guess one could make a case-by-case analysis and see what kind of SAT problem it corresponds to...

As an intermediate question: What is the smallest oriented cycle that has three "top-bottom" runs and is a core? Such an example would be NP-complete by the above discussion.

For the intermediate question (a core with three top-bottom runs), how about this?

Some notation: I will be describing runs by words in $\{l,r\}^*$, with e.g. $llrl$ corresponding to a subgraph $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. The level increases on $r$ arcs and decreases on $l$ arcs, and I assume that its minimum is $0$. Some straightforward constraints are:

There cannot be a run consisting only of $l$s or only of $r$s, because otherwise there is an obvious homomorphism from $D$ to this run (mapping each node of $D$ to the one with the same level). This also implies that the maximum level must be at least $3$.
If the maximum level were $3$, then all top-bottom (resp bottom-top) runs would be of the form $llr(lr)^ill$ (resp. $rrl(rl)^irr)$; again it is not very hard to find a homomorphism from $D$ to the run which minimizes $i$.

However, for maximum level $4$ there is a solution, of length $36$: consider $D$ given by $(rrrlrrlllrll)^3$. This has the required top-bottom runs and is a core (see below). By the above constraints, it is necessarily minimal, since each run only has a single "backwards" edge.

To convince ourselves that this is a core, let's first name the vertices ($v_1,\ldots,v_{36}$). The bottom (i.e. level $0$) vertices are $v_1,v_{13},v_{25}$. Any homomorphism $\varphi$ from $D$ to a subgraph must preserve levels, and in particular $\varphi(v_1)\in\{v_1,v_{13},v_{25}\}$; modulo the obvious automorphism $v_i\mapsto v_{i+12}$, it is enough to consider the case $\varphi(v_1)=v_1$. Consider the neighbourhood of $v_1$ in $D$ (annotated with levels):

$v_{34}(1)\to v_{35}(2)\leftarrow v_{36}(1)\leftarrow v_1(0)\to v_2(1)\to v_3(2)\to v_4(3)\leftarrow v_5(2)\to v_6(3)\to v_7(4)$

Starting with $\varphi(v_1)=v_1$, we have $\varphi(v_2)\in\{v_{36},v_2\}$. But if $\varphi(v_2)=v_{36}$, then $\varphi(v_3)=v_{35}$, and we have no possible value for $\varphi(v_4)$. We get $\varphi(v_2)=v_2,\varphi(v_3)=v_3,\varphi(v_4)=v_4$. Next $\varphi(v_5)\in\{v_3,v_5\}$, but for $\varphi(v_5)=v_3$ we get $\varphi(v_6)=v_4$, with no possible value for $\varphi(v_7)$. So $\varphi$ must be the identity on the entire run $v_1\to\ldots\to v_7$, and by repeating the same argument for the remaining runs, the same is true on all of $D$. In particular, $\varphi$ does not map $D$ onto a proper subgraph.


Two paper appear to imply collapse via coloring $P_5$-free graphs Found this from graphclasses.org.

Two papers give conflicting results for coloring $P_5$-free
graphs  which appear to imply $P=NP$.

From Polynomial-time algorithm for vertex k-colorability of P_5-free graphs

  Abstract. We give the first polynomial-time algorithm for coloring vertices of P5 -free graphs with k colors. This settles an open problem and generalizes several previously known results.

From Some new hereditary classes where graph coloring remains NP-hard, p 5

  ... Coloring is NP-hard in $2K_2$-free ... and $\{C_5,P_5\} \cup \ldots$-free

$2K_2-free \subset P_5-free$ and the other class contains $P_5$.

According to graphclasses, another reason for hardness is
clique cover on the complement (another paper), click +Details
for references.

Question:

  What is wrong with this seeming contradiction?

One of those papers is about k-colorability and the other of

those papers does not specify a constant number of colors.

(For a similar example, consider k-variable-SAT versus SAT.)


Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard? The usage of an $\mathrm{NP}$-oracles which delivers a witness has been proposed for example in [Buss1995]. I would like to see an example of an $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard problem. Can someone tell me?

Since I am not a complexity theory expert, I could not come up with an example nor could I find an example by searching through papers.

References:

[Buss1995] Buss, Krajíček, Takeuti, "Provably total functions in the bounded arithmetic theories $R_3^i$, $U_2^i$ and $V_2^i$" (1995)

$\let\mr\mathrm\def\xx{\mr{FP^{NP[wit,\log]}}}\xx$ is not defined as a class of functions, but of potentially multivalued search problems. It is not difficult to construct $\xx$-complete search problems by variating the usual Cook–Levin theorem. Here is one, somewhat simplified from what I suggested in the comment above.

First, as should be mentioned somewhere in the BKT paper, the class $\xx$ does not change if all the oracle queries are made to ordinary, nonwitnessing NP oracles, except for the final query, which is guaranteed to succeed, and returns a witness $(u,v)$ such that $u$ is the output of the algorithm. Moreover, since $\mr{P^{NP[\log]}}=\mr{P^{\|NP}}$, we can simulate the initial $O(\log n)$ nonwitnessing queries with polynomially many nonadaptive (parallel) NP queries.

Now, if $A(x)$ is a polynomial-time algorithm making $n^c$ nonadaptive queries to an NP-oracle, and one witnessing query in the fashion described above, then

$\qquad B(x,1^j)\iff{}$ “the $j$th parallel query made by $A$ on input $x$ is true”

is an NP-predicate, hence by the Cook–Levin theorem, it is equivalent to the satisfiability of a poly-time (or log-space) constructible 3-CNF. Likewise,

$\qquad C(x,a_1,\dots,a_{n^c})\iff{}$ “the final query is true in the run of $A$ on input $x$ such that the $j$th parallel query is answered with $a_j\in\{0,1\}$ for each $j$”

is an NP-predicate, and the output of $A(x)$ can be read off from a witness to $C(x,\vec a)$ if supplied with the correct $\vec a$. Again, it can be expressed as a 3-CNF. Thus, the following search problem is $\xx$-complete:

  Input: A sequence of 3-CNFs $(\phi_1,\dots,\phi_n)$ (in whatever variables), and a 3-CNF $\psi(x_1,\dots,x_n,y_1,\dots,y_m)$

  Output: A satisfying assignment $(b_1,\dots,b_m)$ to $\psi(a_1,\dots,a_n,y_1,\dots,y_m)$, where
  $$a_j=\begin{cases}1&\text{if $\phi_j$ is satisfiable,}\\
0&\text{otherwise.}\end{cases}$$

Perhaps a more compelling $\xx$-complete problem is the following search variant of MAX-3SAT:

  Input: A 3-CNF $\phi$.

  Output: An assignment that satisfies the maximum possible number of clauses in $\phi$.

To see that this works, let $(\phi_1,\dots,\phi_n)$ and $\psi$ be as in the previous problem, where due to the way the reduction works, we may assume that $\psi(a_1,\dots,a_n,\vec y)$ is satisfiable for every $\vec a\in\{0,1\}^n$. We may also assume that variables used by the $\phi_j$ are pairwise disjoint, and disjoint from $\vec x,\vec y$. Then let $\phi$ be the conjunction of all clauses of $\phi_1,\dots,\phi_n,\psi$, together with a handful additional clauses that express that $x_j$ is true iff all clauses of $\phi_j$ are true.

Given any assignment to variables of $\phi_1,\dots,\phi_n$, we can find an assignment of the remaining variables that satisfies all clauses of $\psi$, and the additional clauses. Moreover, we can change an assignment of the variables of $\phi_j$ without affecting $\phi_k$ for $k\ne j$.

Thus, an assignment satisfying the maximal number of clauses of $\phi$ will also individually maximize the number of satisfied clauses of each $\phi_j$, and in particular, it will satisfy the whole $\phi_j$ iff $\phi_j$ is satisfiable, and its restriction to the $\vec y$ variables will be a correct solution to the original problem.

The above are multivalued search problems. As far as I am aware, it is an open problem whether there are $\xx$-complete functions.

As should also be mentioned in the BKT paper, predicates (i.e., $\{0,1\}$-valued functions) in $\xx$ are computable using nonwitnessing oracles: they are exactly the predicates in the class
$$\Theta_2^{\mr P}=\mr{P^{NP[\log]}}=\mr{P^{\|NP}}=\mr{L^{NP}}.$$
Consequently, a function $f$ is in $\xx$ if and only if

$|f(x)|$ is polynomially bounded in $|x|$, and
the bit-graph of $f$ is in $\Theta_2^\mr P$.

Thus, we could call the class of such functions $\mr{F\Theta_2^P}$. A similar reasoning as above shows that the following is an $\mr{F\Theta_2^P}$-complete function:

  Input: A sequence of 3-CNFs $(\phi_1,\dots,\phi_n)$

  Output: The sequence $(a_1,\dots,a_n)$, where
  $$a_j=\begin{cases}1&\text{if $\phi_j$ is satisfiable,}\\
0&\text{otherwise.}\end{cases}$$

Since $\mr{F\Theta_2^P}$ is closed under composition, an inspection of the two complete problems shows:

  Proposition: The following are equivalent.

  There exists an $\xx$-complete function.
  For every $\xx$-search problem $S(x,y)$, there is an $\mr{F\Theta_2^P}$-function $f$ such that $S(x,f(x))$.
  There is an $\mr{F\Theta_2^P}$-function that computes a satisfying assignment to any given satisfiable 3-CNF.


Is the class of primitive recursion functionals equivalent to the class of functions which Foetus proves to terminate? Foetus, if you have not heard of it, can be read up on here. It uses a system of 'call matrices' and 'call graphs' to find all 'recursion behaviors' of recursive calls in a function. To show that a function terminates it shows that all the recursion behaviors of recursive calls made to a function obey a certain 'lexicographic ordering'. It's termination checker allows all primitive recursive functions and functions such the Ackermann function. Basically it allows multi-argument primitive recursion. This is also basically the the termination checker of Agda; I believe that Coq has some similar facilities as well though perhaps more general.

From reading the paper "Total Functional Programming" by D.A. Turner. He explains that his proposed language would be able to express all "primitive recursive functionals" as seen in System T studied by Godel. He goes on to say that this system is "known to include every recursive function whose totality can be proved in first order logic".

Dose Foetus allow all primitive recursive functionals? If so does it allow functions which are not primitive recursive functionals? Can a citation be provided for the answer to this? (this is not actually necessary as I'm just interested; it's just that some reading marital on the matter would be nice)

Bonus question:
Primitive recursive functionals have a very concise definition in terms of combinators: typed S and K (that can't express the fixed point combinators), zero, the successor function, and the iteration function; that's it. Are there other more general such languages which have such a concise definition and in which all expressions terminate?

Yes, the Foetus checker can typecheck everything in Goedel's T. You can show this by using the checker to show that the iteration operator in T is terminating. For example, the following definition will work:

$$
\begin{array}{lcl}
\mathit{iter}  & : &  A \to (A \to A) \to \mathbb{N} \to A \\
\mathit{iter} \;i \;f \;0 & = & i \\
\mathit{iter} \;i \;f \;(n+1) & = & f\;(\mathit{iter} \;i \;f \;n)
\end{array}
$$

This is very easy for the Foetus checker (or most any other termination checker) to check, because it is an obviously structurally recursive definition.

Agda and Coq both permit proving termination of functions that go far beyond what is provably total in first-order arithmetic. The feature which enables this is that they permit defining types by recursion on data, which is called "large elimination". (In ZF set theory, the axiom scheme of replacement serves roughly the same purpose.)

An easy example of something that goes beyond T is the consistency of Goedel's T itself! We can give the syntax as a datatype:

data T : Set where
   N : T
   _⇒_ : T → T → T

data Term : T → Set where
   zero : Term N
   succ : Term (N ⇒ N)
   k    : {A B : T} → Term (A ⇒ B ⇒ A)
   s    : {A B C : T} → Term ((A ⇒ B ⇒ C) ⇒ (A ⇒ B) ⇒ A ⇒ C)
   r    : {A : T} → Term (A ⇒ (A ⇒ A) ⇒ N ⇒ A)
   _·_  : {A B : T} → Term (A ⇒ B) → Term A → Term B

Note that the type dependency permits us to define a datatype of terms containing only the well-typed terms of T. We can then give an interpretation function for the types:

interp-T : T → Set
interp-T N       = Nat
interp-T (A ⇒ B) = (interp-T A) → (interp-T B)

This says that N should be the Agda natural numbers, and T's arrow should be interpreted as the Agda function space. This is a "large" elimination, because we define a set by recursion on the structure of the datatype T.

We can then define an interpretation function, showing that every term of Goedel's T can be interpreted by an Agda term:

interp-term : {A : T} → Term A → interp-T A
interp-term zero    = 0
interp-term succ    = \n → n + 1
interp-term k       = \x y → x
interp-term s       = \x y z → x z (y z)
interp-term r       = Data.Nat.fold
interp-term (f · t) = (interp-term f) (interp-term t)

(I don't have Agda on this machine, so there are doubtless some missing imports, fixity declarations, and typos. Fixing that is an exercise for the reader, who can also be an editor, if they like.)

I don't know what the consistency strength of Agda is, but Benjamin Werner has shown that the Calculus of Inductive Constructions (Coq's kernel calculus) is equiconsistent with ZFC plus countably many inaccessible cardinals.


Are there digraphs such that any two arborescences are arc-disjoint? Let $D=(V,A)$ be a directed graph with root $r$.
An $r$-arborescence of $D$ is a subgraph such that for any $v\in V-r$, there is exactly one directed path from $r$ to $v$.
Hence an $r$-arborescence is a directed spanning tree whose arcs are directed away from $r$.

Question:
Is there a directed graph $D=(V,A)$ with root $r$ such that any two $r$-arborescences of $D$ are arc-disjoint?

Leaving aside the trivial case (graphs which only have one $r$-arborescence), this won't be possible.

Suppose $(V,E)$ is an $r$-arborescence of $(V,A)$. Then $E$ contains some (nonzero) number of arcs $(r,s_1),\ldots,(r,s_k)$ out of the root (otherwise we are in a trivial case). Now if $(V,F)$ is another arborescence, then either

$F$ also contains some $(r,s_i)$, so the arborescences are not arc-disjoint, or
$F$ contains $(r,t)$ for some $t\notin\{s_1,\ldots,s_k\}$, and for each $i$, an arc $(p_i,s_i)$ for some (not necessarily distinct) vertices $p_1,\ldots,p_k\neq r$. But then we can replace one such arc with $(r,s_i)$ - it is easy to see that $(V,F\cup\{(r,s_i)\}\setminus\{(p_i,s_i)\})$ is again an $r$-arborescence: For any vertex $v$ in the subtree of $(V,F)$ rooted at $s_i$, the only path from $r$ to $v$ is now the old one, with the prefix up to $s_i$ replaced by $(r,s_i)$; for all other vertices, the paths remain unchanged. This new arborescence is distinct from $(V,E)$ since it still contains $(r,t)$, but they are not arc-disjoint since they both contain $(r,s_i)$.