Schaefer's theorem and CSPs of unbounded width Schaefer's dichotomy theorem shows that each CSP problem over $\{0,1\}$ is either solvable in polynomial time or is NP-complete. This applies only for CSP problems of bounded width, excluding SAT and Horn-SAT, for example. General CSP problems of unbounded width may be very difficult (even uncomputable), so let's restrict ourselves to problems which are "natural" and are in NP.

Given a CSP problem of unbounded width, for each $k$, we can look at the restriction of the problem to clauses of width up to $k$. Schaefer's theorem now applies, and the restricted problem is either in P or NP-complete. If for some $k$, the $k$-restricted problem is NP-complete, then so is the unrestricted problem. The situation is less clear when for all $k$, the $k$-restricted problem is in P.

Schaefer's dichotomy theorem relies on four (or so) different algorithms that solve all the easy cases. Suppose that for a given CSP problem, the $k$-restricted problem is always solvable by algorithm A. It might be the case that algorithm A can be used to solve the unrestricted problem as well. Or it might be that algorithm A isn't polynomial time in the unrestricted case, and then we're ignorant as to the hardness of the problem.

Has this kind of problem been considered? Are there examples in which we arrive at the "ignorant" spot?

I claim that for a “natural Boolean CSP,” if the k-restricted version is in P for every k, then the unrestricted version is also in P.  I will define a “natural Boolean CSP” below.

Schaefer’s theorem states that the Boolean CSP on a finite set S of relations is in P if at least one of the following conditions is satisfied and it is NP-complete if none of them is satisfied:

Every relation in S (except for the constant 0) is satisfied by assigning 1 to all its variables.
Every relation in S (except for the constant 0) is satisfied by assigning 0 to all its variables.
Every relation in S is equivalent to a 2-CNF formula.
Every relation in S is equivalent to a Horn-clause formula.
Every relation in S is equivalent to a dual-Horn-clause formula.  (A “dual-Horn-clause formula” means a CNF formula where each clause contains at most one positive literal.)
Every relation in S is equivalent to a conjunction of affine clauses.

Now assume that P≠NP, and consider the case where S is infinite.  If the k-restricted version is in P for every k, then by Schaefer’s theorem, every finite subset of S satisfies at least one of the six conditions above, and this means that the whole set S satisfies at least one of the six conditions.  Does this mean that this CSP without the restriction on arity is also in P?  Not yet.

When S is infinite, we have to specify how each clause in the input formula is given.  We assume that there is some surjective mapping from {0,1}* to S, which specifies the encoding of the relations in S.  A Boolean CSP is specified by giving both S and this encoding function.

Note that in each of cases 3, 4, 5, and 6 above, there is a natural way to represent relations satisfying the condition: a 2-CNF formula in case 3, a Horn-clause formula in case 4, and so on.  Even if a relation is equivalent to (say) a 2-CNF formula, there is no a priori guarantee that its encoding gives an easy access to the 2-CNF formula which is equivalent to it.

Now we say that a Boolean CSP is natural when its encoding function satisfies the following:

  Given an encoding of a relation and an assignment to all its variables, whether the relation is satisfied or not can be computed in polynomial time.  (Note: This ensures that the CSP in question is always in NP.)
  Given an encoding of a relation satisfying condition 3, 4, 5, or 6, its natural representation as specified above can be computed in polynomial time.

Then it is easy to see that if S satisfies one of the six conditions above and the encoding for S satisfies this “naturalness” condition, then we can apply the corresponding algorithm.  The claim which I stated at the beginning can be proved by considering both the case of P=NP and the case of P≠NP.


In-approximability results in severely restricted graph classes Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path $\notin APX$ unless $P=NP$). I don't know if it remains in-approximable in cubic bipartite Hamiltonian graphs. Maximum independent set is not in $APX$ unless $P=NP$ but it is in $APX$ for cubic graphs. David Eppstein pointed out that it is $NP$-complete to find maximum clique in claw-free graphs and it is not clear to me if it is any easier to approximate than in general graphs.

I'm interested in optimization problems that remains in-approximable in severely restricted classes of graphs (for instance, cubic planar bipartite graphs or trees of bounded degree).

A problem $L$ is In-approximable means that  $L \notin APX$. It is $NP$-hard to approximate to any constant factor in polynomial-time.

The labelled perfect matching problem, which consists in finding a perfect matching in an edge-coloured graph that uses the minimum number of colours, is not in APX for subcubic bipartite graphs (but it is $2$-approximable if the maximum degree is $2$ instead of $3$). See Monnot for details.


Completeness of Constraint Typing (type inference) question regarding $\sigma'$ The theorem of completeness of type inference states the following:

Suppose $\Gamma \vdash t:S| _{\mathcal{X}}C$,

In other words, I have some term "t"
whose type is "S" under the assumptions in Gamma,
assuming the constraints "C" is met.
The "x" denotes that we assign the typed variable "x" to this inference.

And sigma is a mapping of type variables to types.

If:

$\sigma(\Gamma)\vdash \sigma(t) : T$, and

When assume a mapping that Gamma has some t whose type is "T".  When we apply
sigma to that Gamma, our assumptions are still valid

$dom(\sigma)\cap\mathcal{X} = \emptyset$

We want the domain of the type mappings to be disjoint from our type variables.

then there is some solution:

$(\sigma', T)= T$ and

The tuple (sigma', T) is equivalent to T

$\sigma'\backslash\mathcal{X}=\sigma$

sigma' set minus type variables will be equal to sigma

What I don't fully understand (and the Pierce book is so very opaque) is why the need for the $\sigma'$ to prove that the program is typeable. What exactly is happening in that transition from $\sigma \rightarrow \sigma'$.

Or am I being as dense as I think, and this theorem is able to simultaneously look at the step rules I have defined for my language and resolve the term to a concrete value.  And Completeness implicitly uses those rules, thus the need for $\sigma'$

Assuming that this is from Chapter 22 of Pierce's book, what's going on is that Pierce had to strengthen the statement of the theorem slightly to deal with all the fresh constraint variables tracked in $\mathcal{X}$.

The naive statement of completeness  would be is that

  If $\Gamma \vdash t:S|_{\mathcal{X}}C$ and $(\sigma, T)$ is a solution for $(\Gamma, t)$, then $(\sigma, T)$ is a solution for $(\Gamma, t, S, C)$.

Basically, this says that if $(\sigma, T)$ is a solution to the type inference problem, then it will be a solution of the generated constraints $C$. However, the inference rules in Figure 22-1 sometimes will create some new contraint variables (for example, rule CT-App), all of which are recorded in $\mathcal{X}$.

If the domain of $\sigma$ overlapped with the new variables constraint generation introduced, then you're in trouble, because now we have the possibility of inconsistencies between $\sigma$ and the constraints in $C$. So, instead Pierce proves that:

  If $\Gamma \vdash t:S|_{\mathcal{X}}C$ and $(\sigma, T)$ is a solution for $(\Gamma, t)$ and $\mathrm{dom}(\sigma) \cap \mathcal{X} = \emptyset$, then there exists a $\sigma'$ such that $(\sigma', T)$ is a solution for $(\Gamma, t, S, C)$ and $\sigma'/\mathcal{X} = \sigma$.

So he says that if $(\sigma, T)$ is a solution for $(\Gamma, t)$ that doesn't overlap with $\mathcal{X}$, then there is a solution $(\sigma', T)$ for $(\Gamma, t, S, C)$ such that $\sigma'$ is an extension of $\sigma$ to cover the variables in $\mathcal{X}$.


Translation from basic While-language to $\lambda$-calculus Is there a simple way to translate programs written in a basic "While" language (such as Winskels Imp)?

I know about Church numerals and booleans, and I can see how if and while statements can be translated as

$$\mbox{if}~t_c~\mbox{then}~t_t~\mbox{else}~t_f\qquad\rightarrow\qquad(t_c t_t)t_f$$ and $$\mbox{while}~t_c~\mbox{do}~t_l \qquad\rightarrow\qquad \omega(\lambda r.(t_c (t_l; \omega r) I))$$ (with suitable definitions for $\omega$ and $I$).

Assignment however puzzles me.

One example translation of the following program

x := foo;
if x then t_1 else t_2

would be

$$(\lambda x.(x t_1)t_2)~foo$$

But I can't seem to find a general rule for it. How would for instance this program translate:

x := true;
y := false;
while x do
    x := y

Here is the toy language I am going to use. Note that locations are numbered.

$$    A := n \quad | \quad x_k \quad | \quad A_1 + A_2 \quad | \quad  ... \text{ (where $n,k ∈ \mathbb{N})$ } $$
$$    B := A_1 = A_2 \quad | \quad  ...  $$
$$    C := \quad  C_1 ; C_2 \quad |\quad  x_k := A\quad  | \quad  skip \quad |\quad \mathop{if}~B~\mathop{then}~C_1~\mathop{else}~C_2 \quad | \quad  ...  $$

First, you have to encode states.
What's a state ? It's map from your set $L$ of locations
to your set $V$ of values. Here I choose to implement them
by a function $σ : \mathbb{N} → \mathbb{N}$. We'll call
$Σ$ the set of states.

There are two common operation over states :
$$\mathop{get} : Σ → L → V$$
$$\mathop{get} = λs.λx.(s~x)$$

$$\mathop{set} : Σ → L → V → Σ$$
$$\mathop{set} = λs.λx.λv.\left(λk.\mathop{equal}~k~x~v~(s~k)\right)$$
where $equal$ is a λ-term representing equality between Church numerals.

Then we have to encode arithmetical expressions as function from $Σ$ to $V$
$$⟦n⟧ = λs.\lceil n \rceil$$
$$⟦x_k⟧ = λs.get~s~\lceil k \rceil$$
$$⟦A_1 + A_2⟧ = λs.\mathop{plus}~(⟦A₁⟧~s)~(⟦A₂⟧~s)$$
$$\vdots$$
where $\mathop{plus}$ is a λ-term representing addition over Church numerals and
$\lceil n \rceil$ is the $n$-th Church numeral.

And boolean expressions as functions from $Σ$ to booleans:
$$⟦A₁ = A₂⟧ = λs.\mathop{equal}~(⟦A₁⟧~s)~(⟦A₂⟧~s)$$
$$\vdots$$

Finally you encode your commands as "state transformers" from $Σ$ to $Σ$.
$$ ⟦skip⟧ = λs.s $$
$$ ⟦x_k := A⟧ = λs.\mathop{set}~s~\lceil k \rceil~(⟦A⟧~s) $$
$$ ⟦C₁;C₂⟧ = ⟦C_2⟧ ∘ ⟦C_1⟧ = λs.⟦C_2⟧~(⟦C_1⟧~s)$$
$$ ⟦\mathop{if}~B~\mathop{then}~C_1~\mathop{else}~C_2⟧ =
   λs.⟦B⟧~s~(⟦C₁⟧~s)~(⟦C₂⟧~s) $$
$$\vdots$$

Exercise 1: Prove the correctness of this compilation wrt to a standard operational semantics.
Exercise 2: Check that everything works in a typed context (you will however need some kind of fixpoint operator to translate the while construction).


Hamiltonian cycle on a subset of 2D points, constrained by maximum total length We are given a list of 2d coordinates, each coordinate representing a node in a graph, and a scalar D, which is a constraint on total length of the cycle. The task is to find a Hamiltonian cycle on a subset of nodes which satisfies all of the following properties:

The total length of the cycle is less than D
The number of nodes included in the cycle is maximal
If there are more solutions satisfying 1. and 2., choose the one having the smallest cycle length

Note that weights of edges satisfy triangle inequality.

I know how to solve a standard shortest Hamiltonian cycle problem. However, I don't know how to choose a subset of points to start with. The naive solution would involve enumerating all subsets of points (NP) and attempting to construct a Hamiltonian cycle on every such subsets (NP again).

It seems totally intractable, even for a small number of nodes (I expect ~15 nodes). The only heuristic I can think of is constructing a minimum spanning tree for every subset, using the length of a MST as a lower-bound estimate and skipping subsets that obviously break constraint #1.

I hope a better solution exists, ideally without enumerating all subsets of nodes.

As RB mentioned, this is the Orienteering problem. For points on a plane, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.5979 gives a PTAS.


Are Shannon entropy and Boltzmann entropy mutually convertible? Are Shannon entropy and Boltzmann entropy mutually convertible, much like mass and energy according to Einstein's formula?

In practice the only difference is that Boltzmann entropy deals with a thermodynamical constant $K_B$:

$
H = -K_B\sum_{i=1}^{N} P_i log_e\ P_i
$

i assume you already know that if $K_B=1$ you have Shannon entropy in a different base.
However the conceptual backgrounds are important; probability of events (Shannon) and probability of a particle being in one of $N$ states (Boltzmann) under a thermodynamical context.

There is theoretical work in making the formal link between the two notions of entropy. Take a look at the work of Edwin Jaynes.

http://en.wikipedia.org/wiki/Edwin_Jaynes


All literals implied by a set of horn clauses What is the name of this problem: given a set of Horn clauses (in fact just definite clauses and facts), find the set of literals which can be deduced from it. E.g. given $\{a, a \Rightarrow b, b \wedge c \Rightarrow d\}$, output $\{a, b\}$.

It's called finding a minimal model of a Horn formula.

This model is unique because the intersection of two models of a Horn formula is itself a model. In fact, [Horn, On sentences which are true of direct unions of algebras, 1951] proved the following: A boolean function can be expressed as a conjunction of Horn clauses if and only if its set of models is closed under intersection.


Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.

It is known that the determinant of an $n\times n$ matrix can be computed in $\tilde{O}(M(n))$ time, where $M(n)$ is the minimum time required to multiply any two $n\times n$ matrices.  It is also known that the best circuit complexity of determinants is polynomial at depth $O(\log^{2}(n))$ and exponential at depth 3.  But the circuit complexity of matrix multiplication, for any constant depth, is only polynomial.

Why is there a difference in circuit complexity for determinants and matrix multiplication while it is known that from an algorithm perspective determinant calculation is similar to matrix multiplication? Specifically, why do the circuit complexities have an exponential gap at depth-$3$?

Probably, the explanation is simple but I do not see it. Is there an explanation with 'rigor'?

Also look in: Smallest known formula for the determinant

Consider circuit value problem and Boolean formula evaluation for various small complexity classes. Deterministic sequential time complexity of them are the similar as far as we know, yet they are very different from circuit complexity perspective. Similarity in one particular type of resource on one model doesn't imply similarity for other resources in other models. One problem can be such that we can exploit parallel computation for one while we can't do that for another one, yet their sequential time complexity can be the same.

When can we expect a more robust relation between the complexity of two problems across models and different resources? When they're are robust reduction between them in both directions that respects resources in those models.

Edit: multiplication has subexponential size depth 3 circuits. Proving a lower-bound of that kind for determinant would show it is not in $\mathsf{NL}$ separating it from $\mathsf{NC^2}$ which is not known.


The relationship between completeness and strength of reductions Ladner theorem can be stated as:

$P \ne NP$ if and only if there exists an incomplete set in $NP-P$.

Here an incomplete set is a set that is not complete for $NP$ under many-one polynomial time reductions (Karp reduction). Therefore, existence of any incomplete problem in $NP$ would immediately imply $P \ne NP$.

  Is there a many-one reduction weaker than Karp reduction for which we can prove the existence of incomplete sets in $NP$?

An example of weak reductions is $NC^0$ many-one reduction (using circuits of polynomial size, constant depth, and bounded fan-in). In an $NC^0$ reduction, each output bit of the reduction can depend only on a constant number of input bits. Many $NP$-complete problems remain complete under $NC^0$ reductions.

  Does there exist an incomplete $NP$ set under $NC^0$ reductions?

If I understand correctly your questions are answered in

Agrawal-Allender-Impagliazzo-Pitassi-Rudich-2001: Reducing the Complexity of Reductions

Gap Theorem - Any set that is NP-complete under $AC^0$ reductions is NP-complete under $NC^0$ reductions.
Stop Gap Theorem - There is a set that is NP-complete under $AC^0[\!\!\mod 2]$
reductions, but not under $AC^0$ reductions.


Motivation for Developing Shortest Path Simplex Algorithms I'm reading Efficient Shortest Path Simplex Algorithms by Donald Goldfarb, Jianxiu Hao and Shen-Roan Kai who considered  "the specialization of the primal simplex algorithm to the problem of finding a tree of directed shortest paths from a given node to all other nodes in a network of n nodes or finding a directed cycle of negative length. Two efficient variants of this shortest path simplex algorithm are analyzed and shown to require at most $(n − 1)(n − 2)/2$ pivots and $O(n^3)$ time."

I'm trying to find motivation for this article and wonder isn't Bellman-Ford algorithm good enough? It works in $O(nm)$ time which and good for the type of graph which the problem above algorithm deals with.

A major open problem in mathematical programming is designing a strongly polynomial time linear programming algorithm. A related problem is whether any variant of the simplex algorithm runs in strongly polynomial time. It makes sense to first prove strong polynomial time bounds for variants of simplex applied to problems for which we already know strong polynomial time algorithms exist.


Books on programming language semantics I've been reading Nielson & Nielson's "Semantics with Applications", and I really like the subject. I'd like to have one more book on programming language semantics -- but I really can get only one.

I took a look at the Turbak/Gifford book, but it's too long-winded; I thought Winskel would be fine, but I have no access to it (it's not in our University library, and I'm short on money), and I'm not even sure if it's not dated. Slonneger seems OK, but the practical part makes it somewhat too long, and I'm not very comfortable with his style.

So my question is -- is Winskel a good book? And is it dated?

Also, are there other concise books on the subject?

It all depends how deep you want to go, and how much you already know. For a beginner Winksel's book is really nice, but yes, it's not introducing you to the state of the art in semantics as it was written about 20 years ago. Nevertheless it's still a good first introduction to the subject. It might also be worthwhile pointing out that T. Nipkow has formalised a substantial chunk of Winskel's book in Isabelle/HOL, see here. So if you want to learn using interactive proof assistants together with understanding the semantics of programming languages, you have a lot of coherent material to draw on.

Other books that are more advanced are:

Gunter, Semantics of Programming Languages, a more advanced book focussing on denotational semantics, an approach to semantics, which hasn't lived up to expectations. Focusses on purely functional lanugages and ignores concurrency. This is the book that I taught myself semantics from as an undergraduate, and in retrospect I wish I had used Winksel's book instead. Gunter is not an easy read for a beginner.
Domains and lambda-calculi by Amadio and Curien. Another book coming written more in the domain-theoretic tradition, although it discusses process calculi.
John Mitchell's books which have already been mentioned above. They are also mostly about sequential computation.

Books like Pierce's TAPL are very nice, but focus narrowly on one aspect of programming languages, namely types, as important as that is. I would not recommend it as a first introduction to the general area of programming languages, but it is mandatory to read for anyone who wants to learn about types.

Truth be told, I think there's currently no up-to-date introductory book on language semantics that reflects the substantial progress the last decade has seen, with its decisive shift away from denotational methods and sequential computation to concurrency (process calculi and game semantics), axiomatics semantics and the use of interactive proof assistants in verification.

Update 22. April 2014: Tobias Nipkow and Gerwin Klein have published a new book

Concrete Semantics

which can be seen as 'Winskel in Isabelle/HOL'. It's an introduction to the
semantics of programming languages (primarily operational and
axiomatic) but unlike previous pen-and-paper-based approaches, this
book expresses all its mathematics in Isabelle/HOL. In other words,
it's at the same time a book about theorem proving.

The book is brand new so I have not used for teaching, but it looks really suitable
as an introduction that is pitched at a lower level than Software Foundations
by
Pierce et al.


Are there links between Geometry of Interaction and Geometric Complexity Theory? I'm very much a novice in these subjects, but Geometry of Interaction and Geometric Complexity Theory seem to speak similar language and have vaguely similar goals. Am I not mistaken? Are there any links between them?

No one knows if there are connections between GoI and GCT.

It's quite plausible, since both are used to analyze complexity, and since GoI is formulated in terms of monoidal categories and GCT is based on representation theory. However, to my knowledge there aren't any researchers who understand both well enough to say for certain.


The Relation between Babbage and von Neumann It is well known that Charles Babbage's analytical machine had an architecture strongly ressembling the modern Von Neumann architecture.

Also, it's notable that the tables for representing a program for Babbage's analytical machine ( http://www.fourmilab.ch/babbage/figures/menat3.png ) and von Neumann's work (such as http://library.ias.edu/files/pdfs/ecp/planningcodingof0103inst.pdf ) are quite analogous.

Now I'm wondering if there's any indication to what extent von Neumann knew of the work done by Babbage, and if he used it as an inspiration for his own work.

In their 2003 paper Lovelace & Babbage and the Creation of the 1843 ‘Notes', John Fuegi and Jo Francis quote H.J. Gray’s Digital Computer Engineering, Prentice-Hall, 1963, in the annoted bibliography given by B. Randell, ed., The Origins of Digital Computers: Selected Papers, Springer Verlag, 1973, p. 420, as saying:

  “John von Neumann urged that all the machine units be connected ... so
  that the machine could be used as a computer of the Babbage type ...
  This was done and ENIAC was operated in this fashion until it
  retired.”


Decidable theory of asymptotic growth What are the known limits of the decidability of the comparison of growth rate of functions from $\mathbb{N} \to \mathbb{N}$? I am here thinking of the decidability of questions like "Is $x^x \sim 2^{\lfloor x \lg (x+2) \rfloor}$?" or "Is $2^{\lg^* x} \in O(\lg \lg x)$?".

If we restrict the functions to be polynomials (expressed in the usual manner), then this isn't hard. See also Cantor normal form.

How large can we make the class of functions before comparison becomes undecidable? Can we extend it to the functions used in a typical undergraduate algorithms class?

As Joshua Grochow explains in the comments, I'm interested really in the set of expressions, not the functions themselves. So, for instance, I'd be interested in decision procedures that could compare "$1$" and "$2$", even if they can't compare "$\ln e$" and "$n^{(\ln n)^{-1}}$".

Possibly related question: "Is the theory of asymptotic bounds finitely axiomatizable?"

Hardy, in his classical book Orders of infinity, considered the class of logarithmic-exponential functions. This is a rather general class of functions, which is the minimal set of functions containing $\mathbb{R}$ and $x$, closed under addition, multiplication and division (unless it has infinitely many zeroes), closed under $\exp$ and $\log|\cdot|$ (same constraint), and closed under solution of polynomial equations (i.e. the function satisfying $f(x)^5 + f(x) = x$ is in the family). Hardy showed that any two such functions can be compared asymptotically. I'm not sure if the proof is algorithmic, but it is worth checking.

Boshernitzan extended this class even further, and doubtlessly there is other work on the subject.


Winning strategy of an "edge or isolated vertex" deletion game Is this perfect information game played on graphs know/studied?

Given a graph $G= (V,E)$, two players alternate picking an edge or an isolated node. If the player picks an edge $e = (u,v)$ the two nodes $u$ and $v$ are deleted along with their incident edges. If the player picks an isolated node, the node is deleted. The first player unable to move loses the game.

What is the complexity of finding the winner?

Any references to similar games?

I post an update as a self-answer only to keep it distinct from the question (which is still open).

As shown in the comments (thanks to Tsuyoshi Ito) the problem is polynomial-time solvable for paths:

$Win(P_n) = 1$ iif $(n \bmod 34) \in \{3,7,23,27\}$

Starting from 0, the (calculated) sequence of the nim values is periodic:

0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
...
the subsequence rseq of length 34:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
is repeated

I didn't work on a rigorous mathematical proof, but the idea is:

suppose that we want to calculate element $Win(P_n), n = k*34 + x \; (k\geq 4, 0 \leq x < 34)$, then the first move (pick an edge) can split the path in $\lceil n / 2 \rceil$  different ways (n-2,0),(n-3,1),(n-4,2),...). The new nim value is equal to:

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$

The first 34 elements of the set are produced by the first non repeating sequence (0,1,1,0,...) (nim)summed with the elements of the repeating sequence in reverse order starting from element $(34-2-x) \bmod 34$.

For example: for $x = 0$:

     0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6 +
     3,4,4,1,1,0,2,1,3,0,1,1,3,2,2,7,5,4,4,3,2,2,3,1,1,0,3,1,2,0,1,1,4,6 =
mex{ 3,5,5,1,3,1,1,1,2,1,2,3,1,1,6,6,0,7,6,1,1,3,2,1,2,1,1,1,3,1,5,5,6,0 } = 4

For x=0..33 the resulting mex sequence is equal to the repeating sequence:

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6

The remaining elements of the set are calulated only on the repeating sequence(s): $rseq[j \bmod 34] + rseq[(34-2-x-j) \bmod 34]$ (for $j \geq 34$ the pairs are repeated, so they don't alter the mex result). The resulting mex sequence for x=0..33 is:

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,4,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,4,

Which is equal to the repeating sequence except for $x=16$ and $x=33$; but the values are lower than the corresponding mex on the non-repeating sequence, so:

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$ = $mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{n-2-33}+P_{33}\}$

and for $(k\geq 4, 0 \leq x < 34)$, $Win(P_{k*34 + x}) = Win(P_{34+x}) = Win(P_x)\; $


Circuits with oracles vs. Turing Machines with oracles Put simply: what is the correspondance between Turing machines with oracles, and uniform circuit families with oracles? How are the latter defined in order to obtain the same computational model, for a given oracle Turing machine?

This may be an elementary question, but it is not obvious where to look, and I'm the sort of person who likes to make sure that my foundations are using good-quality mortar. If there is a standard reference, please point me to it. (Papadimitriou's book, for instance, does not seem to describe circuits with oracles at all.)

My working hypothesis is this: a uniform circuit family with access to an oracle (e.g. for solving an NP-complete problem) is defined as follows:

One defines an infinite family of "oracle gates" On , one for each circuit size n, each of which compute a function fn : {0,1}cn → {0,1} for some constant c.
The functions fn computed by the oracle gates On should be  "uniform" in the following sense: for any n < N and x ∈ {0,1}n, we require fn(x) = fN( 0c(N−n) x ) --- that is, the oracle gates must use a consistent and extensbile "encoding" of their inputs.
One then defines a uniform circuit family, where the oracle gates are among the allowed operations to the circuit, restricting the circuit for input size n to use the gate On.

I imagine that some of the choices above may be arbitrarily fixed without losing any generality. What I am interested in is a reference for the correspondence, or at least  a description of how to modify the description above to obtain the standard one.

The best reference for relativized circuits is Chris Wilson's paper "Relativized NC"  http://www.springerlink.com/content/u727654246wu8662/

The second condition you have (downward closure of O_n) is not needed to get the equivalence say between P^O and uniform poly-size circuits with oracle O. Also your third condition should be thrown away, the size of the circuit will prevent access to O_m for m larger than the circuit size.


When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$? I started reading Avi Wigderson's paper $\mathcal{P}$, $\mathcal{NP}$ and Mathematics – a Computational Complexity Perspective (link).

(Notation: $\{0, 1\}^\ast$ is the set of all finite binary sequences, and $\{0, 1\}_n^\ast$ is the set of all finite binary sequences of length at most $n$.)

In page 7, he defines the complexity class $\mathcal{P}$: A function $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ is in $\mathcal{P}$ if there is an algorithm (i.e. a deterministic Turing machine) that computes $f$, and also a constant $c > 0$ such that the number of steps it takes to compute $f(w)$ for any $w \in \{0, 1\}_n^\ast$ is $O(n^c)$.

Immediately after that he says we that we are going to restrict our attention to the boolean functions $f : \Sigma^\ast \to \{0, 1\}$, since "a function with a long output can be viewed as a sequence of Boolean functions, one for each output bit."

I guess he here intends to say something like this: $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ is in $\mathcal{P}$ if and only if the function $f_i : \{0, 1\}^\ast \to \{0, 1\}$ corresponding to the $i$th output bit is in $\mathcal{P}$ for all $i$.

I find this a bit confusing.

For starters, we are looking at the $i$th output bit, which belongs to $\{0, 1\}$, and we do not have a third symbol to be interpretted as "this bit is empty". This is assuming, of course, that sequences like $0$ and $000\cdots0$ are different. Anyways...

If $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ is in $\mathcal{P}$, then all of its $i$th bit functions are in $\mathcal{P}$ (forgetting about the empty bit problem for now). For any $w$ of length $\leq n$, we compute $f(w)$ in $O(n^c)$ steps, and extract the $i$th bit in $O(i)$ steps, so the bound for $f_i$ is $O(n + i)$.

We can actually bound the $i$s that will produce an output. The Turing machine that computes $f(w)$ will do at most $O(n^c)$ steps, and so the output will be of length $O(n^c)$. Thus $i$ is bounded above by $O(n^c)$.

For the other direction... Here is what I have thought about: Let $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ be such that each of its $f_i$ functions are in $\mathcal{P}$. There is nothing saying their complexity have a uniform bound on their polynomial growth, that is, the time complexity for $f_i$ can be $O(n^{c_i})$ with no bound on the $c_i$, or the number of functions that will produce an output (for the time it will take to put all those bits side by side; that still counts, I think).

Any how, so why can this paper focus on complexity for boolean functions only?

EDIT 1: I just noticed something else: In the definition of $\mathcal{NP}$ (definition 2.3), the verifier function $V_C$ is a function $\{0, 1\}^\ast \times \{0, 1\}^\ast \to \{0, 1\}$ not $\{0, 1\}^\ast \to \{0, 1\}$. I can think of ways to make this work (like encoding $(x, y)$ as an element of $\{0, 1\}^\ast$. For instance, $(x, y) \mapsto 1111110xy = 1^{|x|}0xy$, where the number of $1$s gives the length of $x$. The length of the encoding is $2|x| + |y| + 1 \leq |x|^k + 2|x| + 1$, so we are still fine.)

EDIT 2: Thinking about it some more, the verifier function is a relation $V_C \subseteq \{0, 1\}^\ast \times \{0, 1\}^\ast$ (satisfying the conditions that make it a function). The set $\{0, 1\}^\ast \times \{0, 1\}^\ast$ can be encoded as the subset $C_{\{0, 1\}^\ast \times \{0, 1\}^\ast} = \{1^{|x|}0xy \mid x, y \in \{0, 1\}^\ast\}$, and the indicator function $1_{C_{\{0, 1\}^\ast \times \{0, 1\}^\ast}} : \{0, 1\}^\ast \to \{0, 1\}$ computes the output in linear time. (It exactly includes all the strings of the form $1^n0z$, with $n \geq 0$, and $|z| \geq n$.) A Turing machine can extract $x$ and $y$ from the valid strings belonging to $C_{\{0, 1\}^\ast \times \{0, 1\}^\ast}$ in polynomial time, and follow that with whatever (polynomial) procedure that computes the verifier function. Anyways, the $\mathcal{NP}$ class can be defined building on a definition of the $\mathcal{P}$ class that only involves $\{0, 1\}^\ast \to \{0, 1\}$ functions.

I think you are right that the author's phrasing doesn't seem to immediately suggest a correct formalization of equivalence, but the idea is correct. I think the easiest formalization is the following.

  Given $f: \{0,1\}^* \to \{0,1\}^*$, define:

  $\bar{f}: \{0,1\}^* \times \mathbb{N} \to \{0,1\}$ to be $\bar{f}(x,j) = 1$ iff $|f(x)| \leq j$. (Here $|\cdot|$ is string length.)
  $\hat{f}: \{0,1\}^* \times \mathbb{N} \to \{0,1\}$ to be $\hat{f}(x,j) = f(x)_j$, i.e. the $j$th bit of $f(x)$. If $j$ is larger than $|f(x)|$, the output of $\hat{f}(x,j)$ can be, let's say, always $0$.

Now I will leave it as an exercise to prove that if $f$ is computable in polynomial time, then $\bar{f}, \hat{f}$ are in P; and if $\bar{f}, \hat{f}$ are in P, then $f$ is computable in polynomial time. You do need the idea you mentioned, that $|f(x)| \leq |x|^c$ for some $c$.


Lipton's most influential results Richard J. Lipton has been selected as the winner of the 2014 Knuth Prize  "for Introduction of New Ideas and Techniques".

What are to your minds the main new ideas and techniques that Lipton developed?

Note. This question shall become community wiki, please put one such idea, technique or result per answer.

The Planar Separator Theorem states that in any planar $n$-vertex graph $G$ there exists a set of $O(\sqrt{n})$ vertices whose removal leaves the graph disconnected into at least two roughly balanced components. Moreover, such a set can be found in linear time. This (tight) result, proved by Lipton and Tarjan (improving on a previous result by Ungar) is a powerful tool for designing algorithms on planar graphs. It gives many exact subexponential time algorithms for NP-hard problems and improved polynomial time approximation algorithms. Looking at the wikipedia page gives a good starting place to explore the numerous applications. An early survey with details of a number of applications was written by Lipton and Tarjan in 1980.


Halting on a (possibly one-way) write-once tape Consider Turing machines (with the Busy Beaver "design specifications")
that must write a 1 whenever they read a 1 (i.e., "write once").

${}$1. $\:$ Is the halting problem decidable for these machines?

If those specifications are modified to use a [one-way infinite] tape instead,

${}$2. $\;$ Is the halting problem decidable for the resulting type of machines if they

a. $\;$ stay where they are

b. $\;$ halt

whenever they try to move off the end of the tape?

Ad 1. Write-once TMs are equivalent to ordinary TMs (I think this is an exercise in Sipser, but I don't have the text at hand to confirm) so $\rm woBB$ is uncomputable.

Ad 2. No. The usual zipper encoding also works for write-once TMs, so write-once TMs that never move past the end of the one-way infinite tape are equivalent those with two-way infinite tape. Therefore $\rm owwoBB$ is uncomputable, and the choice of behaviour when moving past the end of the tape doesn't affect this.


Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR? Deutsch's algorithm is a well known quantum computing $f(0) + f(1)\mod{2}$
with only one one evaluation of $f$.
If we replace $+$ with $\cdot$ the problem seems to become rather different. My question is:
does there exist a quantum algorithm computing the value of $f(0)\cdot f(1)$ (or AND if you prefer)
using only one evaluation of $f$. Otherwise: is it known that such an algorithm does not exist?

Update: I have now become aware of procedure that gives correct answer with a probability greater than what any classical procedure is able. The "error" is one-sided in the sense that it always produces the correct answer when $f(0)\wedge f(1)=1$. This leads me to an extended question: does there exist a quentum algorithm (possibly similar to the one mentioned below) with the property that the result is $1$ only if $f(0)\wedge f(1)=1$? Of course the "best case scenario" would be an algorithm that gives correct answer with probability $1$.

This is Assignment 3, Question 5 in Richard Cleve's ongoing intro to quantum computing course. (Seems like this assignment was due today.)

While we're not supposed to answer homework questions on CSTheory, fortunately the assignment answers all your questions. It also takes you through the construction of the quantum algorithm. I strongly recommend reading it.


Impredicativity + large eliminations (with no excluded middle) in Coq It is known that impredicativity + large eliminations + excluded middle is inconsistent. Prop is impredicative and consistent with excluded middle, but does not allow large eliminations (except when constructing witnesses whose type lives in Prop). Set and Type(i) allow large eliminations and are consistent with excluded middle, but are predicative. If we use the -impredicative-set flag, then Set is impredicative, but does not allow large eliminations for large inductive types.
Is there a universe in Coq which is impredicative, allows large eliminations on any inductive type that lives in it, but is consistent in the absence of the axiom of excluded middle?

No: strong elimination of large inductive types (SELIT) is itself inconsistent because it breaks the layering of universes by trivially allowing you to smuggle a large value in a Prop box and take it back out unscathed.
In Is Impredicativity Implicitly Implicit? I proposed a restriction on SELIT which is a bit more permissive than Coq's while still enjoying consistency (I still don't have a proof for it, tho I believe I'm almost there ;-)


Assigning items as evenly as possible Lets say I have a finite set of items like the following:

{$a_1, a_2, ... , a_n$}

And I have a finite list of sets of these items. For example:

[{$a_1$}, {$a_1, a_2$}, {$a_1, a_2, a_3$}, {$a_1, a_3$}, {$a_2$}, {$a_2$}, {$a_2$}, {$a_3$}]

I then take one item from each set. For example, in the above case, I could do:

$a_1$ <- {$a_1$}
$a_2$ <- {$a_1, a_2$}
$a_1$ <- {$a_1, a_3$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1$ <- {$a_1, a_2, a_3$}
$a_3$ <- {$a_3$}

In this case, the totals are:

$a_1$: 3
$a_2$: 4
$a_3$: 1

And the minimum is 1.

But lets say I want to maximise the minimum. I could instead select the items like:

$a_1$ <- {$a_1$}
$a_2$ <- {$a_1, a_2$}
$a_3$ <- {$a_1, a_3$} (changed)
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1$ <- {$a_1, a_2, a_3$}
$a_3$ <- {$a_3$}

And the totals are:

$a_1$: 2
$a_2$: 4
$a_3$: 2

And the minimum is 2.

Lets say also I allow the items to be assigned in a weighted way. Like the following:

$a_1$ <- {$a_1$}
$a_1$ <- {$a_1, a_2$} (changed)
$a_3$ <- {$a_1, a_3$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1: 0.5, a_3: 0.5$ <- {$a_1, a_2, a_3$} (changed)
$a_3$ <- {$a_3$}

And the totals are:

$a_1$: 2.5
$a_2$: 3
$a_3$: 2.5

And the minimum is 2.5.

We can't evenly assign the items in these sets because three of them only contain {$a_2$}.

So what's a fast algorithm for doing the above, i.e. finding the maximum "minimum"? I need something exact, not an approximation.

This can be solved by standard linear programming algorithms.  A set of weighted choices is described by variables $y_{ij}$, where $y_{ij}=w$ if we choose $a_i$ from the $j$th set with weight $w$.  To set this up, we use an additional variable $m$ which will represent the minimum number of times any variable is selected.  We then have four kinds of constraints:

for each $i$, $j$: $0 \le y_{ij} \le 1$ if $a_i$ is in the $j$th set;
for each $i$, $j$: $y_{ij} = 0$ if $a_i$ is not in the $j$th set;
for each $j$: $\sum_i y_{ij}=1$ [choosing a total of 1 element from the $j$th set];
for each $i$: $m \le \sum_j y_{ij}$ [$m$ is at most the number of chosen $a_i$'s].

We choose the $y_{ij}$'s to maximize $m$; the constraints and the objective function are linear.  (In the non-weighted case, we additionally require $y_{ij}$ to be integral; this makes the problem harder but integer linear programming packages are readily available.)

This formulation has the following geometric interpretation.  Identify $a_i$ with the $i$-th standard basis vector in $\mathbf{R}^n$.  For each set, say $\{a_{i_0},\ldots,a_{i_k}\}$, the collection of possible weighted choices from this set is the $k$-simplex with the given $a_{i_j}$'s as vertices.  The Minkowski sum of all these simplices is the convex polyhedron which contains precisely the possible vectors $(x_1,\ldots,x_n)$ of totals for the elements $a_1,\ldots,a_n$.  The linear programming formulation above seeks a point in this polyhedron which is as far from as possible from the nearest coordinate hyperplane.


Survey Article on the Theory of Recursive Functions? Could you recommend a survey article or textbook chapter that introduces the theory of recursive functions? Thanks

A nice reference is "Part C" of Handbook of Mathematical Logic edited by Barwise. Part C includes the following chapters:

Herbert B. Enderton, Elements of recursion theory
Martin Davis, Unsolvable problems
Michael O. Rabin, Decidable theories
Stephen G. Simpson, Degress of unsolvability: a survey of results
Richard A. Shore, $\alpha$-recursion theory
Alexander Kechris and Yiannis N. Moschovakis, Recursion in higher types
Peter Aczel, An introduction to inductive definitions
Donald A. Martin, Descriptive set theory

The chapters are of very high quality and written by leading logicians. This handbook will take you quite far into the world of mathematical logic.


Self-organizing maps algorithm(Kohonen networks) In self-organizing maps(SOM) algorithm described here it is said about the weights of nodes and data items. If using this algorithm for sine function approximation given a few points are the nodes - points and weights - coordinates?

Visualization of clusters.

The same ordered display can be used for illustrating the clustering density in different regions of the data space. The density of the reference vectors of an organized map will reflect the density of the input samples [Kohonen, 1995c, Ritter, 1991]. In clustered areas the reference vectors will be close to each other, and in the empty space between the clusters they will be more sparse. Thus, the cluster structure in the data set can be brought visible by displaying the distances between reference vectors of neighboring units [Kraaijveld et al., 1992, Kraaijveld et al., 1995, Ultsch, 1993b, Ultsch and Siemon, 1990].

The cluster display may be constructed as follows [Iivarinen et al., 1994]. The distance between each pair of reference vectors is computed and scaled so that the distances fit between a given minimum and maximum value, after optionally removing outliers. On the map display each scaled distance value determines the gray level or color of the point that is in the middle of the corresponding map units. The gray level values in the points corresponding to the map units themselves are set to the average of some of the nearest distance values (on a hexagonal grid, e.g., to the average of three of the six distances toward the lower-right corner). After these values have been set up, they can be visualized as such on the display, or smoothed spatially.

The resulting cluster diagram is very general in the sense that nothing needs to be assumed about the shapes of the clusters. Most of the clustering algorithms prefer clusters of certain shapes [Jain and Dubes, 1988].


Evaluating symmetric polynomials Let $f:\mathbb{K}^n \to \mathbb{K}$ be a symmetric polynomial, i.e., a polynomial such that $f(x)=f(\sigma(x))$ for all $x \in \mathbb{K}^n$ and all permutations $\sigma \in S_n$.  For convenience, we can assume $\mathbb{K}$ is a finite field, to avoid addressing issues with the model of computation.

Let $C(f)$ denote the complexity of computing $f$, i.e., the complexity of an algorithm that, given $x$, returns $f(x)$.  Can we somehow characterize $C(f)$, based on the properties of $f$?  For instance, are we guaranteed that $C(f)$ is polynomial (in $n$) for all symmetric polynomials $f$?

As special case, it looks like (a) we can compute the power sum polynomials in time $\text{poly}(n)$, and (b) we can compute the elementary symmetric polynomials in time $\text{poly}(n)$, using Newton's identities.  As a consequence, if $f$ is a weighted sum of monomials where no variable is raised to a power higher than 1 (i.e., if $f$ is multilinear), then $f$ can be computed in polynomial time (since it can be expressed as a weighted sum of elementary symmetric polynomials).  For instance, when $\mathbb{K}=GF(2)$, then every symmetric polynomial can be computed in polynomial time.  Can one say anything more than this?

The question seems quite open ended. Or perhaps you wish to have a precise characterization of the time-complexity of any possible symmetric polynomial over finite fields?

In any case, at least to my knowledge, there are several well-known results about the time-complexity of computing symmetric polynomials:

If $f$ is an elementary symmetric polynomial over a finite field then it can be computed by polynomial-size uniform $TC^0$ circuits.
If $f$ is an elementary symmetric polynomial over a characteristic $0$ field, then it can be computed by polynomial-size depth three uniform algebraic circuits (as you already mentioned the Newton polynomial; or by the Lagrange interpolation formula); and so I believe this then translates to polynomial-size uniform Boolean circuits (though perhaps not of constant depth) (but this may depend on the specific field you're working in; for simplicity you might consider the ring of integers; though for the integers I presume $TC^0$ is enough to compute symmetric polynomials in any case.)
If $f$ is a symmetric polynomial over a finite field then there is an exponential lower bound on depth three algebraic circuits for $f$ (by Grigoriev and Razborov (2000) [following Grigoriev and Karpinsky 1998]). But, as mentioned in 1 above, this corresponds only to constant-depth Boolean circuit lower bounds (while there are small uniform Boolean circuits in $TC^0$; meaning also that the polynomials are computable in polynomial-time).

Probably there are more known results about the time-complexity of symmetric polynomial...


question about probability ranking principle I am studying IR and

I am not clearly understand  "probability ranking principle" ( I tried to google the definition, but i couldn't find clear answer.)

I am assuming that it's system which response to each request is a ranking of the documents in the collection in order of decreasing probability.

but, I am not clearly understand concept of probability ranking principle

does anyone can explain it ?

thanks

This is a clear definition of the probability ranking principle.

If a reference retrieval system's response to each request is a ranking of the documents in the collection in order of decreasing probability of relevance to the user who submitted the request, where the probabilities are estimated as accurately as possible on the basis of whatever data have been made available to the system for this purpose, the overall effectiveness of the system to its user will be the best that is obtainable on the basis of those data.

As an IR professional (I work on Google Local Search), the principle is definitely wrong in the case that you assume the searcher doesn't examine every result and is just looking for one to satisfy their request.  Imagine you have 10 results that are excellent independently, but are near duplicates of each other.  Then the probability that the user finds something relevant barely increases as you spend results on the duplicate documents.  If you would have shown a diverse set of results with just one of the excellent, non-duplicate results, and others that satisfy the a secondary interpretation of the query, you'd do better to satisfy the user.

On the other hand, if your evaluation metrics for a set of results are just a sum of independent, result level metrics, then the principle is certainly correct.  You want to maximize the relevance of each result, and you can do that by picking the best ones in a vacuum.


Is it possible to convert any tree to a B-tree or an R-tree? I have a tree structure representing sentences. My tree's nodes are characterized by a type (sentence, phrase, or word), unique ID, text value and an arbitrary number of features. Each node has an arbitrary number of directed edges linking it to other nodes (i.e. children, parent and different grammatical relations such as subject_of, complement_of, etc.). Note that all these features are absolutely necessary to accurately represent the syntactical structure of a sentence.

Now, given such an initial tree with a totally unconstrained structure, I want to know if it is possible to convert that tree into a form that is more search-efficient (i.e. so that search involves less recursion). The only operation I really need to support is finding nodes with an arbitrary combination of type, id, value, and/or feature(s). I also need to be able to match a node back to the original tree if other operations are necessary. What is of primary importance is read-time and query efficiency.

From what I understand, B-trees and R-trees are generally search efficient. From Wikipedia, "like B-trees, this makes R-trees suitable for large data sets and databases, where nodes can be paged to memory when needed, and the whole tree cannot be kept in main memory." This is exactly the situation I am in right now. However, I have very limited knowledge of the different types of trees and how they convert to another.

So, I am wondering if it is possible in theory to convert any N-ary tree (i.e. in my case, a completely unconstrained tree with an arbitrary number of children, edges and features for each node) into a B-tree or an R-tree to make it more search efficient? How would one go about doing this?

An N-ary tree is the general term describing a tree data structure containing/organizing a list of numbers.

A B-tree is an N-ary tree opimized for block/disk access. Each leaves contain ranges of elements.

An R-tree is an N-ary tree but the order imposed on the list of elements is no longer the "greater than" order on a list of numbers but a"close to" metric on points in 2D and more. The "close to" metric is approximated by bounding boxes. An R-tree can be implemented over a B-tree, technically speaking.

Furthermore, any data set in n-dimensions has representations in 1D. Therefore, given some metric, all these tree topologies are isomorphic...


Complexity of $\{0,\pm1\}$ determinant in sparse cases? If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity?

Assume that the matrix is given in form a list where $1,-1$ locations are and so the presentation is only $O(n)$ sized.

Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$.

If the answer to your question were positive, then you could compute the determinant of an arbitrary symmetric $n \times n$ $\{0,1\}$ matrix $M$ (=adjacency matrix of an undirected graph, possibly with self-loops) in $O(n^2)$ time. As the algebraic complexity of matrix multiplication and the determinant are essentially the same, this comes very close* to showing the exponent of matrix multiplication is 2.

More precisely: given a matrix $M$ as above, embed it as the upper-left corner of an $n^2 \times n^2$ matrix as follows:

$M' = \left(\begin{array}{cc} M & 0 \\ 0 & I_{n^2-n} \end{array}\right)$

Then $M'$ is an $N \times N$ matrix $(N=n^2)$ satisfying your conditions, and $\det M' = \det M$, so if your question had a positive answer then we could compute $\det M' = \det M$ in $O(N) = O(n^2)$ operations.

*-The main differences are: (1) using bit complexity, and (2) restriction to $\{0,1,-1\}$ entries. However, while it is possible, I have little reason to suspect that these restrictions significantly change the complexity of matrix multiplication from $O(n^\omega)$.


Complexity of higher order residues Let $P$ be a prime. Given a number $a$, what is the computational complexity in establishing if $a$ is a cubic or higher order residue modulo $P$? Are there any good algorithms?

Yes, there are good (efficient) algorithms.  This is completely solved, and the algorithms are widely used in the cryptographic community.

If $\gcd(n,p-1)=1$, then everything is a $n$th residue.

If $n$ divides $p-1$, then $a$ is a $n$th residue if and only if $a^{(p-1)/n} \equiv 1 \pmod p$.

If $1<\gcd(n,p-1)<n$, $a$ is a $n$th residue if and only if it is a $\gcd(n,p-1)$-th residue (see previous case).

For more details, see Finding roots in ℤp on Crypto.SE.


Type systems preventing laziness-related memory leaks? Perhaps the main source of performance problems in Haskell is when a program inadvertently builds up a thunk of unbounded depth - this causes both a memory leak and a potential stack overflow when evaluating. The classic example is defining sum = foldr (+) 0 in Haskell.

Are there any type systems which statically enforce lack of such thunks in a program using a lazy language?

Seems like this should be on the same order of difficulty as proving other static program properties using type system extensions, e.g. some flavors of thread safety or memory safety.

Levy's call by push value calculus makes a distinction between values and their thunks.  For a value v of type ty the computation thunk v has type U ty.  Lindley and McBride's Frank language, inspired by CBPV, also makes this distinction between computations and values explicit, though unlike Haskell, Frank is strict.


Implications of faster randomized $CIRCUIT SAT$ algorithm In here on page $13$ proposition $1$ it says 'If $CIRCUIT$ $SAT$ on $n$ inputs and $m$ gates is in $2^{n^{o(1)}}poly(m)$ time, then $EXP\not\subseteq P/poly$'.

Can we have randomized $2^{n^{o(1)}}poly(m)$ time in above statement?
Is there a similar result that would give $E\not\subseteq SIZE(2^{\delta n})$ (this would give $P=BPP$)?
How large can $o(1)$ be in the statement above and in 1. if applicable (can it be as large as $1/\log\log n$)?

The gist of the proof of the proposition you're talking about is to simply cite that $EXP\subset P/poly$ implies $EXP=\Sigma_2^p$ (there is a short proof of this in the Arora and Barak book in the chapter on circuit complexity), and then you can show using this time $2^{n^{o(1)}}poly(m)$ Circuit SAT algorithm that $\Sigma_2^p\subseteq DTIME[2^{n^{o(1)}}]$, which contradicts the time hierarchy theorem (I can edit in a hint for this if this is desirable).

If we replaced the assumption, we would no longer get anything we know to be a contradiction in the above argument. As one of the comments mentioned, it is currently open whether $ZPP=EXP$, and even a substantially weaker version of the proposition with a randomized algorithm would give us this separation (note, as the comment says, $BPP$ and $ZPP$ are contained in $P/poly$).
It is known that if $P = NP$ (so in the flavor of the above, if Circuit SAT has a $poly(n+m)$ time algorithm), we get exponential size lower bounds against $E$. This follows as we know $E^{\Sigma_2^p}$ has exponential size lower bounds, and if $P=NP$, then $E=E^{\Sigma_2^p}$. I'm not sure who this argument first came from, but the idea is that using a $\Sigma_2^p$ oracle, on an input $x$ of length $n$, we can find the lexicographically first truth table of an $n$-bit boolean function with the maximum circuit complexity over $n$-bit boolean functions in time $2^{O(n)}$. After doing this, we can simply look up the value of $x$ in this truth table and output accordingly. In doing this, not only are we computing a function which requires exponential sized circuits, but we are actually showing, as Ricky pointed out in the comments, that $E^{\Sigma_2^p}$ has a language of maximum circuit complexity.  Also, to clarify a point mentioned in the post, to get $P=BPP$, you actually need that $E$ does not even infinitely often have circuits of size $2^{\delta n}$. This does follow from $P=NP$, but it is a stronger hypothesis than $E\not\subset SIZE[2^{\delta n}]$.
The argument above works for any runtime that falls into $2^{n^{o(1)}}$, so this includes $2^{n^{1/\log\log(n)}}$.


Logspace algorithms on graphs with bounded tree width Tree width measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known approximation algorithm achieves $O(\sqrt{{\log}n})$ factor.

Courcelle's theorem states that any property of graphs definable in monadic second-order logic (MSO2) can be decided in linear time on any class of graphs of bounded tree width. A recent paper showed that Courcelle's theorem still holds when "linear time" is replaced with "logspace". However, this does not settle the space complexity of Graph Isomorphism on graphs with bounded tree width. The best known result puts it in LogCFL.

Are there other problems that are :

NP-hard (or not known to be in P) on general graphs, and
known to be solvable in linear/polynomial time on graphs with bounded tree width, and
NOT known to be in LogSpace ?

Tutte polynomial is an example.

This is a generalization of the chromatic polynomial, which itself is a #P-hard problem in any reasonable formulation. In

  Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width, S. D. Noble,
  Combinatorics, Probability and Computing, 1998,

a polynomial time algorithm is given where the time complexity is about $O(f(k)n^{4+\epsilon})$, where $k$ is the treewidth and $n$ is the number of nodes.
Related works can be seen in here. For a survey, there are article on Arxiv,
where the complexity issue discussed in section 8.

It seems that the problem cannot be expressed in MSO2 directly, though I'm not familiar with the detailed definitions... Hope this problem is what you need!


What is a commutative transitive closure operator? When reading about descriptive complexity theory, I have read about a "commutative transitive closure operator". I understand transitive closure operators, but what is a commutative transitive closure operator?

Take a relation $R \subseteq X \times X$. Now, let $R^\dagger$ be the converse relation to $R$, and let $\Delta_X$ be the identity relation on $X$.

The commutative transitive closure $R^*$ is the smallest relation $S $ such that $\Delta_X \cup R \cup R^\dagger \cup S \circ S \subseteq S$.

Intuitively, think of the relation $R$ as being the edge relation on a directed graph. The commutative transitive closure tells you whether or not there is a path between two nodes, if you let yourself ignore the directedness.


Turing machines whose termination is unprovable? I have a naive question: does there exist a Turing machine whose termination is true but unprovable by any natural, consistent and finitely axiomatizable theory? I ask for a mere existence proof rather than a specific example.

This might have some connection with ordinal analysis. Indeed, for a Turing machine $M$, we can define $O(M)$ as the least ordinal of a consistent theory proving its termination (or the infimum of these ordinals). So I guess it would be equivalent to ask whether there exists $M$ such that $O(M) \geq \omega_1^{CK}$?

Termination of a Turing machine (on a fixed input) is a $\Sigma^0_1$ sentence and all usual first-order arithmetic theories are complete for $\Sigma^0_1$ sentences, i.e. all true $\Sigma^0_1$ statements are provable in these theories.

If you look at totality in place of halting, i.e. a TM halts on all inputs, then that is a $\Pi^0_2$-complete sentence and for any computably axiomatizable consistent theory which is strong enough (e.g. extends say Robinson's $Q$ theory) there is a TM whose totality cannot be proven in that theory.


Closure properties of deterministic context-sensitive languages There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages.

However, the literature is almost mute on the subject of the closure properties of deterministic context-sensitive languages. In fact, I have spend days looking for it on the internet and in the standard reference books about formal languages and theoretical computer science and didn't find anything complete or related enough to bother using and I wasn't able to find results let alone proofs for most properties myself either.

So, let $\mathbf{DCSL}$ denote the class of deterministic context-sensitive languages, then given two arbitrary languages $L_1, L_2 \in \mathbf{DCSL}$ and a regular language $L_R$, what are its closure properties under

union, $L_1 \cup L_2 \in \mathbf{DCSL}$
intersection, $L_1 \cap L_2 \in \mathbf{DCSL}$
set difference, $L_1 \setminus L_2 \in \mathbf{DCSL}$ (or $L_1 - L_2 \in \mathbf{DCSL}$ to remove ambiguities with left quotient)
complementation, $L_1^c \in \mathbf{DCSL}$
concatenation, $L_1 L_2 \in \mathbf{DCSL}$
Kleene star, $L_1^* \in \mathbf{DCSL}$
intersection with a regular language, $L_1 \cap L_R \in \mathbf{DCSL}$ (bonus)
left/right quotient with a regular language, $L_1 / L_R \in \mathbf{DCSL}$ and $L_R \backslash L_1 \in \mathbf{DCSL}$ (bonus)
reversal (bonus)
homomorphism, maybe $\lambda$-free homomorphism (bonus)
inverse homomorphism (bonus)
substitution, maybe $\lambda$-free substitution (bonus)

These are probably not all interesting closure properties of languages, but for now, I think they are enough.

Posting only results is acceptable, but providing proofs or counterexamples is definitely preferred.

To clarify the notion of deterministic context-free language: a language $L$ is deterministically context-sensitive, if there exist a formal grammar $G$ such that $L_G = L$ and all production rules of $G$ are unambiguous and consist of either growing[1] or strictly growing[2] context-sensitive substitution patterns.

Note: There are two slightly different kinds of unambiguous context-sensitive grammar classes and probably two slightly different kinds of deterministic context-sensitive language classes as well (unless they coincide, which I highly doubt since their nondeterministic counterparts don't), namely [1] and [2]. For the questions posed above, both are relevant and may yield different answers.

Note: AFAIK A (strictly) growing grammar/language is also called a (strictly) monotonic grammar/language by some authors

This question moved over from Computer Science beta

Some  results

Unless I am very mistaken, some of these questions are not hard. But I did not yet look at all of them.

I assume that a deterministic context-sensitive language (DCSL) is
defined as one recognized by a deterministic linear bounded automaton
(DLBA). We note $n$ the size of the input string $w$. We restrict the
problem, w.l.o.g, to DLBAs that use a tape that has the size of the
input string, plus the two end markers. We also assume that acceptance
is by terminating (no transition) accepting state, and rejection is by
terminating non-accepting state or non-termination.

The constructions below will use multi-track finite tapes. That is
only a presentation of a single tape that is the cross-product of
several tapes, i.e. where each cell can contain a tuple of symbols,
one component of the tuple for each track.

Since the tape contain initially just the input string, a first
deterministic pass of any DLBA we build will consiste in
transforming the input tape into a multitrack tape, that will have the
initial string in one or several of its tracks.

For every DLBA $A$, there is a DLBA $A'$ that always halt and accepts the same language.

The problem here is to detect looping computation. That is done with
the pigeon-hole principle, using the fact that computation is deterministic.

A first point is to note that a DLBA has $O(nk^n)$ configuration,
where $k$ is the number of tape symbols of the DLBA, the factor $n$ is
for the head position, and the constant number of states is just a
constant factor.  Hence, using a constant $h$ large enough (usually
$k+1$, but it may not be enough for small values of $n$, though that
is just a finite number of cases), a tape track of size $n$ with an
alphabet of size $h$ is enough to count beyong the number of
configurations of $A$ for the given input.

Hence we can build a DLBA $A'$ that has three tracks, two to simulate
the original DLBA $A$, and the other to simulate the counter. The
roles of the two simulation track are to hold the tape configuration
for the first, and to memorize the head position and the associated
state for the second.

The finite control, simulates steps of the automaton $A$ one at a
time, and  increment the counter by one for each simulated transition.
If the counter overflow the tape, then the number of steps simulated
exceeds the number of possible configurations of $A$, which indicates
that $A$ went at least twice through the same configuration, hence
that it is looping for ever since computation is deterministic.

In such a case, the DLBA $A'$ stops in a rejecting state.

Otherwise, the DLBA $A'$ accepts or rejects as $A$ would have.

*So, W.l.o.g., we can now consider only DLBA that always terminate.

Complementation of (the language of) a DLBA $A$

Given a terminating DLBA accepting a language $L$, we can construct a
DLBA accepting its complement $\bar L$ by exchanging accepting and
non-accepting states.

Thus DCSLs are closed under complementation.

Intersection, union, and difference of (languages of) two DLBA $A$ and $B$.

We assume wlog that both DLBA always terminate. Hence it is easy to
build a DLBA $C$ with two track, each containing initially a copy of
the input (after the initialization pass, as indicated above). The
DLBA $C$ will first simulate $A$ until it terminates, then simulate
$B$ until it terminates. Then it can examine the terminating states of
both, and mimic any bolean function on the results, particularly and
for intersection and or for union.

This gives closure of DCSLs under union, intersection, and set difference.

Closure of DCSLs under intersection with regular set is just a special case, as
any DFA is a DLBA.

Concatenation of (languages of) two DLBA $A$ and $B$.

It is easy to check whether a string $w$ is accepted as the
concatenation of two strings $u\in\mathcal L(A)$ and $v\in\mathcal
L(B)$. Knowing where the boundary between $u$ and $v$ is placed, a
DLBA $C$ can simulate $A$ on $u$, then $B$ on $v$ and decides on
acceptance iff both simulations accept.

The remaining difficulty is that given a string $w$, we do not know
how it should be decomposed as $w=uv$ such that $u\in\mathcal L(A)$
and $v\in\mathcal L(B)$. The solution is to try successively all
possible decompositions, until one succeeds, which is followed by an
acceptance. If none succeed, the input string $w$ is rejected.

Hence DCSLs are closed under concatenation.

Kleene star of (the language of) a DLBA A

This problem is nearly the same as concatenation. But instead of
trying all decompositions of the input string $w$ into two strings, we
have to try all possible decomposition into the concatenation of an
arbitrary number of  non-empty substrings. To do this, the simplest
way is to use a track to keep a clean copy of the input string, a
track to have a working copy on which we test a decomposition in
substring, and a third track with a $\{0,1\}$ alphabet that defines
the decomposition into substrings. To list all the possible
decompositions, we only have to use the third track as a counter from
$0$ to $2^{n-1}-1$, incrementing it by one after every unsuccesful
try, until one succeeds thus accepting the input string, or until the
counter reaches the value $2^{n-1}$ in which case the input string is
not accepted.

Thus DCSLs are closed under Kleene star

Note: Closure of DCSLs under reversal is just obvious


Proving proof system properties within the proof system itself? While reading about Frege proof systems in [1], I came across the completeness theorem and its proof, which involves a few lemmas introduced first. Here are the first two of those lemmas:
$$\begin{equation} \vdash \phi \supset \phi \tag{1} \end{equation}$$
$$\begin{equation} \Gamma, \phi \vdash \psi \space \text{if and only if} \space \Gamma \vdash \phi \supset \psi \tag{2} \end{equation}$$
The first one is easy to prove using the axioms and inference rule of Frege proof system. The proof of the second one uses induction. This confused me a bit and prompted the following questions:

Are proof systems "self-contained", in the sense that their properties can be proven within themselves? Or are properties such as soundness and completeness "external" to the system? The rationale being part of the motivation for proof systems to formalize proofs and thus serve as a foundation of sorts for other math.
Is there some "strange loop" going on when using something like induction (which is defined on the natural numbers) to prove such properties? Also, $\Gamma$ is a set, which is not really part of this proof system vocabulary. For example, if you use a sound but incomplete proof system $P$ to prove the soundness and completeness of another proof system $Q$, does that imply that $Q$ can't "express" $P$ somehow, since that would be paradoxical?

Sorry if my question is ill-posed. I'm a beginner to this topic, so I would appreciate any advice on formulating the question correctly as well.

[1] Buss, Samuel R. (ed.), Handbook of proof theory, Studies in Logic and the Foundations of Mathematics. 137. Amsterdam: Elsevier. 811 p. (1998). ZBL0898.03001.
[2] https://en.wikipedia.org/wiki/Semantic_theory_of_truth

There is no loop. The purpose of a formal system is to make reasoning principles explicit and to explain more precisely how reasoning works. The word "foundation" in "foundations of mathematics" does not mean "create a secure base for mathematics out of nothing" – that would be an indifensible position.
There is absolutely nothing wrong with a logicians using sets to describe a formal system. Should a number theorist not be allowed to use numbers? Are logicians allowed to use strings of symbols? Where do you draw the line?
On the technical side of things, there are formal systems that can talk about their own syntax and proof rules. After all, that is the gist of Gödel's incompleteness theorems: he shows that as soon as a formal system contains arithmetic, it can speak about syntax and its own provability.


Paradigms for complexity analysis of algorithms Worst-case and average case analysis are well-known measures for the complexity of an algorithm. Recently smoothed analysis has emerged as another paradigm to explain why some algorithms which are exponential in the worst-case work so well in practice, for instance the simplex algorithm.

My question is - are there any other paradigms to measure the complexity of an algorithm? I'm particularly interested in ones that attempt to explain why some algorithms which have bad worst-case complexity work well in practice.

There are natural variants of worst-case analysis that are also useful. Perhaps the most famous one is parametrized complexity. Here, we consider a "two-dimensional" measure: the usual input length $n$ and some additional non-negative integer $k$, the parameter. Even though an algorithm may run horribly in the worst case (for all values of $n$ and $k$), it could be that all the cases in one's application that needs to be solved, this parameter $k$ happens to be low, so the algorithm runs well on those instances.

For example, suppose you want to solve Maximum Independent Set on some class of graphs, and develop an interesting algorithm that is surprisingly fast. Investigating further into the class of graphs themselves, you find that all the graphs you examine just happen to have treewidth at most $10$. Well, Bodlaender (cf. Neidermeier [1]) showed that when the treewidth is k, Max Independent Set is fixed parameter tractable: it can be solved in $O(2^k (|E|+|V|))$ time. This gives some explanation as to why your algorithm works well.

[1] R. Niedermeier, Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2006.


Is there a non-deterministic linear time algorithm for CNF-SAT? The decision problem CNF-SAT can be described as follows:

Input: A boolean formula $\phi$ in conjunctive normal form.

Question: Does there exist a variable assignment that satisfies $\phi$?

I'm considering several different approaches for solving CNF-SAT with a non-deterministic two-tape Turing machine.

I believe that there is an NTM that solves CNF-SAT in $n \cdot \texttt{poly}(\log(n))$ steps.

Question: Is there an NTM that solves CNF-SAT in $O(n)$ steps?

Any relevant references are appreciated even if they only provide near linear time non-deterministic approaches.

This is only an extended comment.
A few times ago I asked (myself :-) how fast a multitape NTM that accepts a (reasonably encoded) NP-complete language can be. I came up with this idea:

3-SAT remains NP-complete even if variables are represented in unary. In particular we can convert a clause - suppose $(x_i \lor \neg x_j \lor x_k)$ - of an arbitrary 3-SAT formula $\varphi$ on $n$ variables and $m$ clauses in a sequence of characters over alphabet $\Sigma = \{ +, -, 1 \}$ in which every variable occurrence is represented in unary:

$ + 1^{i} 0,- 1^{j} ,+ 1^{k} $

For example, $(x_2 \lor -x3 \lor +4)$ can be converted to:

+110-1110+11110

So we can convert a 3-SAT formula $\varphi_i$ in an equivalent string $U(\varphi_i)$ concatenating its clauses. The language $L_U = \{ U(\varphi_i) \mid \varphi_i \in 3-SAT \}$ is NP-complete.

A 2-tape NTM can decide if a string $x \in L_U$ in time $2|x|$ in this way.

the first head scans the input from left to right and with the internal logic it keeps track when it enters or exit a clause or reach the end of the formula. Whenever it finds a $+$ or $-$, the second head starts moving right with it on the $1^i$ that represents $x_i$. At the end of $1^i$, if the second head is on a $0$ then it guesses a truth value $+$ or $-$ (it makes an assignment) and writes it on the second tape; if it finds a $+$ or $-$ then that variable has already been assigned a value;
in both cases, using the internal logic, the NTM matches the truth value under the second head (the assignment) with the last seen $+$ or $-$; if they match then the clause is satisfied;
then the second head can return to the rightmost cell;
with the internal logic the NTM can keep track if all clauses are satisfied while the first head moves towards the end of the input.

Example:

Tape 1 (formula)    Tape 2 (variable assignments)
+110-1110+11110...  0000000000000...
^                   ^
+110-1110+11110...  0000000000000...
 ^                  ^
+110-1110+11110...  0000000000000...
  ^                  ^
+110-1110+11110...  0+00000000000... first guess set x2=T; matches +
  ^                  ^               so remember that current clause is satisfied
+110-1110+11110...  0+00000000000...
  ^                  ^
...
+110-1110+11110...  0+00000000000...
    ^               ^
...
+110-1110+11110...  0++0000000000... second guess set x3=T
       ^              ^              don't reject because current
                                     clause is satisfied (and in every
                                     case another literal must be parsed)

The time can be reduced to $|x|$ if we add some redundant symbols to the clause representation:

$ + 1^{i} 0^i,- 1^{j} 0^j ,+ 1^{k} 0^k \; ... \; \text{+++}$

($\text{+++}$ marks the end of the formula)

In this way the second head can return to the leftmost cell while the first scans the $0^i$ part.
Using $\text{++}$ as a clause delimiter and $\text{+++}$ as a marker for the end of the formula we can use same representation for CNF formulas with an arbitrary number of literals per clause.


Why have computer scientists chosen recursor instead of iterator in primitive recursion? I wonder why computer scientist have chosen recursor instead of iterator (or tail recursor if you like) in primitive recursion, given that function defined in terms of iteration behaves more efficiently than that in terms of recursion.

EDIT:

Let us go further, do you think iteration would be better than recursion to complexity?

Iterators of any kind are just a form of recursion, i.e., a thing "using itself". For example, the basic equation governing the while loop is

  (while b do C)  =  (if b then (C; while b do C))

You may think I am doing something exotic, but as soon as you try to explain what recursion and iteration mean, you will end up writing such equations. For example, people tend to explain the while loop by saying things like "and so on" (imprecise) or "do C while b" (not explaining anything), or "keep doing" (circular explanation). The above equation tells you everything there is to know about the while loop. Similar arguments can be made about other forms of iteration.

The above equation is recursive, as the defined term appears on both sides. The general form is $$x = \phi(x),$$ which of course is just a general recursive definition of $x$. In this sense iteration is just a special form of recursion. So as far as theory is concerned, there is pratically no difference between recursion and iteration, except that the latter is a special case of the former. And both concepts are special cases of fixed point equations, a very important and general mathematical concept. This answers why "they chose recursor instead of iterator".

Your claim that iteration is more efficient than recursion is bogus. Modern programming languages are quite efficient at both of these tasks. In any case, it is not the job of humans to think about low-level details of execution of programs (maybe that was the case in the 1960's when the total amount of CPU power and memory on the planet was comparable to what kids carry in their pockets these days). We have better things to do as programmers, such as how to write programs most efficiently and how to make sure they are actually correct.


Semantic vs. Syntactic Complexity Classes In his "Computational Complexity" book, Papadimitriou writes:

  RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the basis of defining a language in RP. For a machine N to define a language in RP, it must have the remarkable property that on all inputs it either rejects unanimously, or it accepts by majority. Most nondeterministic machines behave in other ways for at least some inputs ... There is no easy way to tell whether a machine always halts with a certified output. We informally call such classes semantic classes, as opposed to the syntactic classes such as P and NP, where we can tell immediately by a superficial check whether an appropriately standardized machine indeed defines a language in the class.

Several pages later, he points that:

language L is in the class PP if there is a nondeterministic polynomially bounded Turing machine N such that, for all inputs x, $x \in L$ iff more than half of the computations of N on input x end up accepting. We say that N decides L by majority.

Question 1: Why Papadimitriou concludes that PP is a syntactic class, while its definition is only slightly different from that of RP?

Question 2: Whether being "semantic" for a complexity class is equivalent to NOT having complete problems, or the lack of complete problems is thought of as a property that we GUESS semantic classes possess?

Edit: See related topic Do all complexity classes have a leaf language characterization?

RP involves a promise, that either 0 paths accept or more than half accept, no matter what the input is. For PP, there is no such promise. If more than half the paths accept, then $x \in L$, otherwise, $x \notin L$. (PP can be defined so that the acceptance criteria are $\geq 1/2$ and $< 1/2$ respectively.)

Or in other words, if I give you a probabilistic TM claiming it is a PP machine deciding some language, you can be sure that it decides some language. Clearly, the language it decides is this one: Try input $x$. See if more than 1/2 of the paths accept (or more than 1/2 random strings cause it to accept). If so, $x \in L$. If not, $x \notin L$. So we've defined a language using this TM.

On the other hand, if I give you a probabilistic TM claiming it is a RP machine deciding some language, you can't even be sure that it decides any language. The problem is that when you observe only a few paths accepting, you don't know if $x$ is in $L$ or not. So if I give you a RP machine, you just have to take my word for it. Indeed, checking if this machine defines a language is uncomputable.

As for your second question, for syntactic classes usually there's an obvious complete problem, which is like "Given machine M, decide if it accepts in time T on input x." If you're given a nondeterministic machine, this problem is NP-complete, if it's a PP-machine, then it's PP-complete, etc. The obvious complete problem for semantic classes is undecidable, as I mentioned. So we don't get a complete problem for free for semantic classes. But a semantic class can have a complete problem. For example if P = BPP (as is widely believed), then BPP has a syntactic characterization.

EDIT: Since there's some discussion on how to define semantic and syntactic classes, I'd like to point out that Papadimitriou gives a definition in his book when talking about leaf languages. (See my question about leaf languages for some references.)

He says that syntactic classes are those for which there exists some language that defines the class using the leaf language technique. Semantic classes are those for which all such characterizations require promise problems. This is a rigorous definition, but only works for those languages that have leaf language characterizations.


Are there languages that are not in RE nor CO-RE? I am familiar with the theorem which states that some languages are not in the RE (Recursively Enumerable) class of languages, but that can mean either that they are all in CO-RE (or rather, the part of it that doesn't intersect with RE), or that they are partly in CO-RE and partly somewhere else.

Are there languages about which nothing can be decided, not even what words are not in them?

Yes, there are some. There is actually an infinite hierarchy of languages which are less and less decidable, namely the Arithmetical hierarchy. Recursively Enumerable languages and their complements are at its level 1. An example of language which isn't RE or coRE is the set of Turing machines computing total functions.


A curious asymmetry in good characterizations There are quite a few theorems, mostly in graph theory and combinatorial optimization, that are often referred to as good characterizations. They typically put a property in $NP\cap co-NP$, by showing that a property either holds, or else there is some well identified obstacle that prevents it from holding. Often they are presented as min-max theorems, see the earlier question Optimization problems with good characterization, but no polynomial-time algorithm

Here are two classical examples of good characterizations:

A bipartite graph either has a matching of size $k$, or else there are less than $k$ vertices that cover all edges. The existence of such a cover is a trivial obstacle that excludes the matching. If this obstacle is not there, the matching must exist, this is the nontrivial part, known as Konig's Theorem.
Either there is an $s-t$ flow of value $F$ in a flow graph, or else there is an $s-t$ cut with capacity less than $F$. Again, the existence of such a cut is a trivial obstacle, since then the flow cannot get through. The nontrivial part is that the absence of the obstacle already guarantees the existence of the flow of value $F$, which is equivalent to the Max Flow Min Cut Theorem.

What I find a curious feature in these (and many other) results is that they show a well visible  asymmetry in the proof hardness between the two directions of the equivalence. Usually, it is easy, or even trivial, to prove that the obstacle excludes the considered property. On the other hand, it is much harder to prove that the easy/trivial obstacle is the only obstacle, in the sense that once it is not there, the property must hold.

I am not aware of  a good explanation why this type of asymmetry is so common. It does not appear a priori necessary. Note: do not get misled by the fact that the above examples are both special cases of linear programming duality. There are other examples that have nothing to do with linear programming.

  Question: Do you know any good characterization that does not fall in this category? (Admittedly, it is vaguely defined, but perhaps the idea got through.) In other words, I am looking for a theorem that puts a property in $NP\cap co-NP$, by capturing all possible obstacles of the property, but they are not all easy/trivial obstacles.

(This is to answer Sasho Nikolov's comment, but it is way too long for the comment field, so I post it as an answer.)

The two examples in the original question are special cases of LP duality. There are many similar examples, but one can argue that they all inherit the asymmetry from LP duality. Weak LP duality is easy to prove (it provides the "trivial obstacle"), while strong duality is deeper, proving that the trivial obstacle is the only obstacle. In this sense, the examples that are "children of LP" may be viewed that they are only different incarnations of the same core example.

Here are, however, some other cases that (to my knowledge) are not related to LP. The examples below are all from graph theory, but other fields probably also contain similar patterns.

Let $k, l, d$ be positive integers. Then there is a simple graph with vertex-connectivity $k$, edge-connectivity $l$, and minimum degree $d$, if and only if $k\leq l \leq d$. Since it is (almost) trivial to prove that these parameters always satisfy the inequalities, the violation of at least one inequality is a trivial obstacle for such a graph to exist. The other direction, that such a graph always exists is nontrivial.
(See the book of Bollobas "Extremal Graph Theory," Theorem 1.5. Note: the way it is presented there is somewhat more complicated, using more inequalities, because it also uses another parameter, the number of vertices. But this simpler version can be extracted from it, to show the essential nature that here again the trivial obstacle is the only obstacle.)
Given an undirected simple graph, does it have two vertex-disjoint circuits?
This is answered by the following theorem of Lovasz and Dirac: If a simple graph with minimum degree $\geq 3$  does not have two vertex-disjoint circuits, then the graph can only be one of the following three types: (1) $K_5$, (2) a wheel graph, (3) $K_{3,n-3}$, with possibly any edges added to the the 3-vertex class. Here the trivial obstacle is that the graph falls into one of these types, since these types are easily seen not to contain 2 vertex-disjoint circuits. If the trivial obstacle is absent, the graph always has the property (but it is quite nontrivial to prove).
Given a sequence $d_1\geq\ldots\geq d_n$ of integers, and an integer $k\geq 2$, does there exist a $k$-edge connected simple graph that has $d_1\geq\ldots\geq d_n$ as its degree sequence? A 1964 result of Edmonds answers the question: such a graph exists if and only if two conditions hold: (a) the sequence is graphical (i.e., there is a graph at all that implements it as a degree sequence, which is trivially necessary, and can be checked  by the Erdos-Gallai Theorem), and (b) $d_n\geq k$, which is also trivially necessary, since the edge connectivity is bounded from above by the minimum degree. Once these essentially  trivial necessary conditions are satisfied, the desired graph always exists.
Given a complete graph $G$, and a fixed graph $H$, can the edges of $G$ be partitioned into disjoint copies of $H$? A 1976 theorem of Wilson proves that if $G$ is sufficiently large, then the only obstacle for such a partition to exist is the violation of one the following trivially necessary divisibility conditions: (a) $|E(H)|$ is a divisor of $|E(G)|$, (b) if $g$ is the greatest common divisor of the degrees of $H$, then $g$ is a divisor of $|V(G)|-1$.


NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with entries in $\{0,1\}$ that maximizes the number of vectors $v_i$ having positive dot product with $x$.

For example, for the collection of vectors given by the rows of the matrix
$$ \begin{bmatrix} -1 & -1 & -1 & -1 \\ +1 & +1 & -1 & -1 \\ +1 & -1 & +1 & -1 \\ -1 & +1 & +1 & -1 \\ -1 & -1 & -1 & -1 \end{bmatrix} $$
the optimal choice of $x$ is $[1,\ 1,\ 1,\ 0]^T$, which has positive dot products with the middle three rows.

Is this problem known to be NP-hard? If so, are any polynomial-time approximation algorithms available?

(Cross-post from mathoverflow here: https://mathoverflow.net/questions/288136/np-hardness-of-finding-0-1-vector-to-maximize-rows-of-1-1-matrix)

This problem is NP-hard. In fact, even deciding whether there exists a choice of x such that all the dot products are positive is NP-complete. I show this below by reduction from set cover.

Reduction

Suppose we are given a set cover instance consisting of number $k$ and sets $S_1, S_2, \ldots, S_m \subseteq \{1,2,\ldots,n\}$. The corresponding question is whether there exists a subset $C$ of $\{1,2,\ldots,n\}$ with $|C| = k$ such that each $S_i$ contains at least one element of $C$ (or equivalently such that $S_i \cap C$ is non-empty for each $i$).

We use this input to construct an instance of your problem, that is, a set of vectors over $\{-1, 1\}$ of the same length. The length of these vectors is going to be $n+k+1$, and there will be $m+k+2$ of them. In particular, we will have vectors $a$, $b_1, b_2, \ldots, b_{k+1}$, and $c_1, c_2, \ldots, c_m$ as defined below.

Denote by $1(n)$ a vector of length $n$ whose values are all $1$s. Denote by $e_i(n)$ a vector of length $n$ whose $i$th value is $1$ and whose other values are $-1$. Denote by $s_j$ a vector of length $n$ whose $i$th value is $1$ if $i \in S_j$ and $-1$ otherwise.

Then

$a = [~1(k+1)~;~-1(n)~]$
$b_j = [~e_j(k+1)~;~1(n)~]$ for $1 \le j \le k+1$ and
$c_j = [~-e_1(k+1)~;~s_j~]$ for $1 \le j \le n$

Correctness

Let $x = [~x'~;~x''~]$ be any vector of $0$s and $1$s expressed as two subvectors $x'$ and $x''$ of lengths $k+1$ and $n$.

Suppose that the dot product of $x$ with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$ is positive. Then consider the two vectors $a$ and $b_j$ (for some $j$). These two vectors are almost exactly negatives of each other. In particular, they both have $1$ as the $j$th component but are otherwise negatives of each other (this is easy to verify). Then if $x$ is a vector of $0$s and $1$s with a $0$ in the $j$th component, the dot product of $x$ with $a$ is the negative of the dot product of $x$ with $b_j$. In this case, these two dot products cannot both be positive. Therefore, $x$ must have a $1$ in the $j$th component.

The above logic can be applied for every $j$ with ($1 \le j \le k+1$). From this, we can conclude that if $x$ has a positive dot product with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$, then $x' = 1(k+1)$.

Furthermore, we know that $x \cdot a > 0$, and $$x \cdot a = [~x'~;~x''~] \cdot [~1(k+1)~;~-1(n)~]= [~1(k+1)~;~x''~] \cdot [~1(k+1)~;~-1(n)~] = 1(k+1) \cdot 1(k+1) + x'' \cdot -1(n) = k+1 - |x''|_1$$ where $|x''|_1$ is the number of $1$s in $x''$, so $k+1-|x''|_1 > 0$ and $|x''|_1 < k+1$.

Similarly, $x \cdot b_1 > 0$, and $$x \cdot b_1 = [~x'~;~x''~] \cdot [~e_1(k+1)~;~1(n)~]= [~1(k+1)~;~x''~] \cdot [~e_1(k+1)~;~1(n)~] = 1(k+1) \cdot e_1(k+1) + x'' \cdot 1(n) = -(k-1) + |x''|_1,$$ so $-(k-1)+|x''|_1 > 0$ and $|x''|_1 > k-1$.

Together the above implies that $|x''|_1 = k$. To summarize, we have shown that if $x$ has a positive dot product with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$, then $x' = 1(k+1)$ and $|x''|_1 = k$. In fact, it is easy to verify that the reverse is also true. In other words, $x = [~x'~;~x''~]$ has a positive dot product with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$ if and only if $x' = 1(k+1)$ and $|x''|_1 = k$.

From now on, consider only vectors $x$ of the above form. Notice that there is a one to one correspondence between possible vectors $x''$ and subsets of $\{1, \ldots, n\}$ of size $k$: in particular, $x''$ can be put into correspondence with set $X \subseteq \{1, \ldots, n\}$ with $|X| = k$ such that $(x'')_i = 1$ iff $i \in X$.

Under this correspondence, we can consider the necessary and sufficient conditions for $x$ to have positive dot product with vectors $c_1$, $\ldots$, and, $c_n$.

For any $j$, we can expand $x \cdot c_j$ as $$x \cdot c_j = [~1(k+1)~;~x''~] \cdot [~-e_1(k+1)~;~s_j~] = 1(k+1) \cdot -e_1(k+1) + x'' \cdot s_j = (k-1) + x'' \cdot s_j.$$
Notice that the value of $x'' \cdot s_j$ is exactly a sum of $k$ components of $s_j$: in particular, $x'' \cdot s_j = \sum_{i \in X}(s_j)_i$. If these $k$ components are all $-1$s, then this sum is $-k$, and so $x \cdot c_j = (k-1) + x'' \cdot s_j = (k-1) + -k = -1 < 0$. If these $k$ components include at least one $1$, then this sum is at least $-1\times(k-1) + 1\times 1 = -(k-2)$ in which case $x \cdot c_j = (k-1) + x'' \cdot s_j \ge (k-1) + -(k-2) = 1 > 0$. Thus, we see that $x \cdot c_j \ge 0$ for a specific $j$ if and only if $X$ includes at least one $i$ such that $(s_j)_i = 1$.

Remember that $(s_j)_i = 1$ if and only if $i \in S_j$. Thus, $x \cdot c_j \ge 0$ for a specific $j$ if and only if $X$ includes at least one $i$ such that $i \in S_j$, or equivalently if and only if $X \cap S_j$ is non-empty.

Then $x \cdot c_j \ge 0$ for every $j$ if and only if for every $j$, $X \cap S_j$ is not empty. Notice that the latter condition is exactly equivalent to the condition that $X$ is a solution to the input set cover instance.

In summary, we see that $x$ is a vector of $0$s and $1$s with positive dot product with all the vectors produced by the reduction if and only if $x = [~1(k+1)~;~x''~]$ with $|x''|_1 = k$ and $x''$ corresponds to a set $X \subseteq \{1, \ldots, n\}$ with $|X| = k$ such that $X$ is a solution to the input instance of set cover. In other words, a solution to the set cover instance exists if and only if a solution to the instance produced by the reduction exists.


Online to batch sample complexity It is well known that a mistake bound can be converted to a PAC bound. I know how to prove a sample complexity of
$$ O( (1/\epsilon)[M + \log(M/\delta)] ), $$
where $M$ is an upper bound on the number of mistakes.
I am told that Nick Littlestone sharpened this to
$$ O((1/\epsilon)[M + \log(1/\delta)])$$
in his 1989 COLT paper. Can anyone describe the proof, or better yet, help me find a copy of this paper? Is this the best possible?

Here is the sketch of a proof I know.
Let us draw $s = \max\left(\frac{4M}{\varepsilon},\frac{c}{\varepsilon} \log\frac{1}{\delta}\right)$ samples from the unkown distribution (where $c$ isconstant), and feed them as input for the mistake-bounded algorithm. We can assume the learning algorithm is conservative, i.e., only changes its working hypothesis after an incorrect prediction has been made.

Look at the sequence of $k \le M$ hypothesis produced by the learner; we claim that, with probability $1-\frac\delta2$, at least one of them has error $< \frac\varepsilon2$. Assume the contrary and observe that any hypothesis with error $\ge \frac\varepsilon 2$ will be found to be wrong within the next $\frac{2}\varepsilon \le \frac{s}{2M}$ random examples on average. Therefore the expected number of samples before the last hypothesis is produced is bounded by $s / 2$. By using a Chernoff-like bound for the sum of geometric random variables, we can bound the probability that a hypothesis with error $< \frac \varepsilon 2$ is not found within $s$ samples by $\delta / 2$ (for a suitable value of $c$).

The rest is easy: we know that one of the hypothesis is good, so we just draw $O\left(\frac{1}{\varepsilon} \log{\frac{M}{\delta}}\right)$ additional samples, test each of them against this new sample set, and select the best one. By Chernoff bounds, it holds that with probability $1-\frac\delta 2$, the good one has empirical error $< \frac{3}{4} \varepsilon$ on this set, while any wrong hypothesis with error $> \varepsilon$ will have empirical error $> \frac{3}{4} \varepsilon$. All in all, a hypothesis with error less than $\varepsilon$ will be selected with probability $1-\delta$.

My guess is that the bound is optimal, but I haven't found a reference for this.