Data representation affecting problem complexity Given some problem, could you have a situation where the problem is shown to be in P, assuming you start with a particular representation of the problem and some data structures, but that if the problem data was represented in some other way then the problem would become NP? (or some other complexity classes)

In other words have any problems been stated to be in P when this depends on the input data being formatted in a way that a would-be algorithm-user wouldn't necessarily have available so the complexity of the problem becomes drastically changed by needing to convert the data first?

This question comes from wondering how knots can be represented and wondered how this would affect comparing whether two knots are the same?

Although not (yet) getting all the way down to $\mathsf{P}$, Group Isomorphism and other algebraic problems can depend heavily on the format of the input, in a way that is far more subtle than merely padding. For example, when the groups are given by multiplication tables, there is a trivial $n^{\log n + O(1)}$-time algorithm to test isomorphism. When the groups are given by generating sets (say, of permutations, or of matrices over finite fields), there are slightly sub-exponential algorithms, but the problems are at least as hard as Graph Isomorphism. When the groups are given by generators and relations, the problem is undecidable (indeed, when given by generators and relations, even telling if the group is trivial or not is undecidable, whereas this particular task is trivial in the other mentioned formats).

Another algebraic example is provided by Grobner bases. Most questions about ideals in polynomial rings become comparatively easy if you're given a Grobner basis for the ideal instead of an arbitrary generating set. But computing a Grobner basis is $\mathsf{EXPSPACE}$-complete. (This is perhaps not as good an example, since it is a property of the input, rather than a the format of the input that is affecting complexity here. But I thought I'd mention it anyways.)


Is there any problem which is in AWPP but conjectured to be not in BQP? Is there any known problem which is in $\mathsf{AWPP}$ but conjectured to be not in $\mathsf{BQP}$? What about relative to an oracle?

Is there any known problem in $\mathsf{MQ^2}$ which is conjectured to be not in $\mathsf{BQP}$?

The relationship of $\mathsf{AWPP}$ to $\mathsf{BQP}$

$\mathsf{AWPP}$ is the class of languages $L$ for which, for each $\varepsilon \in 2^{-O(\mathop{\mathrm{poly}} n)}$,
there is $g \in \mathsf{GapP}$ and $f \in \mathsf{FP}$,
such that

for $x \notin L$ we have $0 \leqslant \frac{g(x)}{f(x)} \leqslant \varepsilon$ and
for $x \in L$ we have $1-\varepsilon \leqslant \frac{g(x)}{f(x)} \leqslant 1$.

This is a [technical but relatively well-known] upper bound for the class $\mathsf{BQP}$. Its relationship to other "gap-defined classes" could be summarised as
$$ \mathsf{SPP \subseteq LWPP \subseteq WPP \subseteq AWPP \subseteq PP}, $$
where $\mathsf{LWPP}$ is notable as a [once more technical but relatively-well known] upper bound on $\mathsf{EQP}$ (with algebraic coefficients over any constant set), and $\mathsf{SPP}$ is the gap-definable version of $\mathsf{UP}$. Thus all of these contain $\mathrm{UNIQUE\text-SAT}$.
By Valiant-Vazirani and the closure of $\mathsf{BQP}$ under subroutines, if $\mathrm{UNIQUE\text-SAT} \in \mathsf{BQP}$, we then have $\mathsf{NP \subseteq PH \subseteq BQP}$. We may reasonably consider this to be unlikely, so $\mathrm{UNIQUE\text-SAT}$ is an easy example of a problem in $\mathsf{AWPP}$ which one may consider unlikely to be in $\mathsf{BQP}$ (albeit a problem which belongs to classes which "seem much smaller" than $\mathsf{AWPP}$ as well).
The relationship of $\mathsf{MQ^2}$ to $\mathsf{BQP}$
The class $\mathsf{AWPP}$ also upper bounds the following (not generally well-known) class defined by Tušarová [arXiv:cs/0507057]:

$\mathsf{MQ^2}$ is the class of languages $L$ for which there is

a [concisely] poly-time computable family $\bigl\{ T_n \bigr\}_{n \geqslant 1}$ of unitary matrices [i.e. a family of matrices $T_n$ such that the function $(j,k,n) \mapsto \left\langle j \:\!\right\vert \!\!\; T_n \!\!\;\left\vert \:\!k \right\rangle$ can be computed in polynomial time, and where we probably want to impose the restriction to functions computing coefficients over a finite-degree extension of the rational numbers]

a poly-time computable string-valued function $I$, and

a poly-time computable predicate $\alpha$ on strings,

such that $\displaystyle\sum_{c : \alpha(c,x) = L(x)} \Bigl\vert\langle c \:\!\lvert\;\! T^2 \!\!\:\ \rvert I(x) \rangle\Bigr\vert^2 \geqslant \tfrac{2}{3}$  [the exponent on the $T$ is significant here].

(In the definition above, we let $L(x) \in \{0,1\}$ denote the characteristic function of $L$.)
The functions $I$ and $\alpha$ serve the role of classical pre-processing and post-processing, respectively, in a quantum algorithm in which we have somehow managed to perform a quite possibly complicated unitary, twice in succession.
The input state $\lvert I(x) \rangle$ is a standard basis state which could be efficiently computed by deterministic classical computation, and $\alpha$ serves to deterministically compute whether a possible measurement outcome $\lvert c \rangle$ is a possible "accepting state" for the problem instance $x$.
It is not clear that $\mathsf{MQ^2}$ is comparable to $\mathsf{BQP}$. The operator $T$ in the definition of $\mathsf{MQ^2}$ is specified by its coefficients rather than as a tensor network, so Solovay–Kitaev does not suffice to allow $\mathsf{BQP}$ to simulate such operators; and clearly we do not expect the coefficients of a tensor network such as a quantum circuit family to be easily evaluated, so the reverse containment would also be surprising.
The class $\mathsf{MQ^2}$ is itself not really well-known enough for there to be any common conjectures about it. (This question is the only place I'm aware of it being discussed, apart from the eprint by Tušarová.) But I get the impression that if the native problem of $\mathsf{MQ^2}$ — that of simulating (the square of) an exponentially large matrix with efficiently specifiable coefficients — is in $\mathsf{BQP}$, the techniques used to show this may have important implications for quantum circuit synthesis, and may shed light on the question of $\mathsf{BQP \mathrel{?\!\!\:=} BPP^{BQNC}}$. Thus, if not unlikely, this result would be quite interesting.


Testing feasibility of special linear programs We have a linear program in the standard form $Ax=b,x\geq 0$ with $A(i,j)\in\{-1,0,1\}\:\forall\,i,j$ and $b(i)\in\{0,1\}\:\forall\,i$. $A$ is not full rank. Is the time complexity of testing the feasibility of this LP any better than that of general LPs? If yes, is there an algorithm known? Thanks in advance.

My first observation: we know how to solve your LPs in strongly polynomial time, but this is an open question for general LPs.


Church-Rosser equivalent for concatenative languages? Looking at the striking parallels between combinatory logic and concatenative languages makes me wonder how many theorems of the former hold in the latter. The Church-Rosser theorem is particularly interesting because it would justify the use of transparent quotations. Is there any concatenative programming language proven to be Church-Rosser?

SK combinators are Church-Rosser.

However, the usual  $\lambda$-calculus method of proving local confluence and then appealing to Newman's lemma doesn't work. You need a slightly fancier argument, and the SEP entry on combinatory logic gives a sketch of a proof that does work.


NP-intermediate problems with efficient quantum solutions Peter Shor showed that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) only yields a quadratic improvement over the classical algorithm, hinting that NP-complete problems are still intractable on quantum computers. As Arora and Barak point out, there's also a problem in BQP that is not known to be in NP, leading to the conjecture that the two classes are incomparable.

Is there any knowledge/conjecture as to why these NP-intermediate problems are in BQP, but why SAT (as far as we know) isn't? Do other NP-intermediate problems follow this trend? In particular, is graph isomorphism in BQP? (this one doesn't google well).

Graph isomorphism is not known to be in BQP. There has been a lot of work done on trying to put it in. A very intriguing observation is that graph isomorphism could be solved if quantum computers could solve the non-abelian hidden subgroup problem for the symmetric group (factoring and discrete log are solved by using the abelian hidden subgroup problem, which in turn is solved by applying the quantum Fourier transform on abelian groups).

One of the ways people have tried to solve graph isomorphism was by applying the quantum Fourier transform for non-abelian groups. There are algorithms for the quantum Fourier transform for many non-abelian groups, including the symmetric group. Unfortunately, it appears that it may not be possible to use the quantum Fourier transform for the symmetric group to solve graph isomorphism; there have been quite a few papers written about this which show that it doesn't work, given various assumptions on the structure of the algorithm. These papers are probably what you find when you google.


Efficient verification of Kemeny-optimal rankings The problem of finding a Kemeny optimal aggregation is as follows: Given items $1 \ldots n$ and a list of partial rankings $q_i$ (i.e. permutations of subsets) of these items, find a ranking $r$ of $1\ldots n$ that minimizes $\sum_i d(r, q_i)$. Where $d(r, q)$ is defined as a count of the number of pairs on which $r$ and $q$ agree, scaled so that complete agreement is 1 (i.e. scaled by $k(k-1)/2$ where $k = |q|$).

Finding a Kemeny-optimal solution is known to be NP-hard in n (not surprising, it's an optimisation problem on a search space of size $n!$). What I'm wondering is if it's in fact NP-complete - if there's an (efficient?) polynomial time algorithm for verifying if a given ranking is in fact Kemeny optimal. I've seen a paper or two claiming it is, but I've not been able to find any papers which prove it. (Possibly because I live and work outside the academic firewall). Any references / ideas?

The following decision problem is NP-complete:
Kemeny Score
Input: An election ($n$ partial or full rankings of $m$ candidates) and a positive integer $k$.
Question:: Is there a ranking with $\sum_i d(r, q_i) \leq k$?

This decision problem is often seen as "natural decision problem" behind Kemeny voting. It is trivially in NP since computing the Kendall-Tau distance is in P. For NP-hardness see for example [Bartholdi, Tovey and Tick, Social Choice and Welfare 1989] or [Dwork, Kumar, Naor, and Sivakumar, WWW 2001].

However, the problem you describe above looks more like an optimization problem. To answer your question I refer to the Kemeny Winner problem which is $P_{||}^{NP}$-complete (see [Hemaspaandra, Spakowski, Vogel, TCS 2005]). Thus, already deciding whether a candidate is an (optimal) winner in Kemeny's system is presumable not in NP.


Huffman Tree Depth, Is there any theory? I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without drawing tree.

Specific Example is : 10-Input Symbol with Frequency 1 to 10 is 5. the above question mentioned depth is 5.

I don't know of a way to compute the length of the code exactly without constructing a Huffman code. And there may be more than one optimal Huffman code for a given set of weighted items, with different lengths. But there has been some related theory on lengths of Huffman codes:

Length-limited Huffman coding is a variant of Huffman coding where you are not allowed to use codewords longer than a given threshold. One can construct an optimal length-limited code in time $O(nL)$ where $n$ is the number of items and $L$ is the length bound; it is unknown whether this can be improved to match the time of unrestricted Huffman coding. See Larmore and Hirschberg, "A fast algorithm for optimal length-limited Huffman codes", JACM 1990, and Turpin and Moffat, "Practical length-limited coding for large alphabets", Computer J. 1995.

The length-limited problem was introduced earlier by Gilbert, "Codes based on inaccurate source probabilities", IEEE Trans. Inf. Th. 1971, who also showed that it is possible to restrict the length to log_2 n + (log log n)^{1+o(1)} while increasing the expected length by at most one. In "Restructuring ordered binary trees", J. Alg. 2004, Evans and Kirkpatrick write that restricting the length more strongly, to ceiling(log_2 n)+1, can force the expected length increase to be arbitrarily close to one. Evans and Kirkpatrick show that this strong length restriction can be obtained, even for alphabetic codes, with an expected increase in length of two.


Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses? We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$.

Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$.

$\mathsf{PP}$ still seems like it would be of reach.

What evidence do we have that $\mathsf{P} \neq \mathsf{PP}$, under that assumption, i.e., evidence that does not apply to $\mathsf{P}$ vs. $\mathsf{NP}$?

$\underline{\mbox{Assumption}}$: Note if $\mathsf{SAT}$ is in linear time then perhaps $\mathsf{P=PSPACE}$ might follow as composition of linear time is linear time?

$\underline{\mbox{Following is only based on if above assumption follows}}$:

Perhaps the problem would be

1a. why believe $\mathsf{SAT}$ is in superlinear time

1b. and if there is reason to believe $\mathsf{SAT}$ is in superlinear time then why believe $\mathsf{PP}$ requires $\Omega(\log\log n)$ quantifications?
Do evidences provided by https://eccc.weizmann.ac.il/report/2018/107/ and http://arxiv.org/abs/1504.03398 still hold up in face of $\mathsf{P=NP}$ and $\mathsf{SAT}$ in linear time ($\mathsf{P=NP}$ seems to invalidate second)?

The scaled down version of $\mathsf{PH}$ versus $\mathsf{PP}$ is $\mathsf{AC}^0$ versus $MAJ \circ \mathsf{AC}^0$, and we know that for the latter there is an exponential separation. Of course, this separation doesn't propagate exponentially up, but you could take this as philosophical evidence that $\mathsf{PH}$ is different enough from $\mathsf{PP}$ that perhaps that remains true even if $\mathsf{P} = \mathsf{NP} = \mathsf{PH}$. (In fact, following this line of reasoning, I'd guess you can build an oracle relative to which $\mathsf{P} = \mathsf{NP} \neq \mathsf{PP}$.)


Regular expressions: Finding "negation" of regular expression? Given regular expressions containing only (,),|,* and characters of an Alphabet A, how can I find the "negation" of a regular expression i.e.:

<R1> is a regular expression
<R2> = A*\<R1>

where A* are all the words you can produce with A and <Ri> the words accepted by the regular expression Ri.

Given R1, how can I find R2? Is there any algorithm to do that?

Thank you!

As another answer already states, the standard approach is: converting to a DFA, complementing, and converting back to a regular expression takes two exponential steps in the worst case (one for obtaining the equivalent DFA, and one for converting its complement to a regular expression).

This is essentially optimal in the worst case: There are examples of regular expressions of length $n$ such that the shortest regular expression describing complement provably has length at least $2^{2^{c \cdot n}}$, where $c$ is some fixed constant; Such examples are known already for alphabets of size $2$. (Gelade & Neven 2008, and Gruber & Holzer 2008).

Wouter Gelade, Frank Neven: Succinctness of the Complement and Intersection of Regular Expressions. STACS 2008: 325-336
Hermann Gruber, Markus Holzer: Finite Automata, Digraph Connectivity, and Regular Expression Size. ICALP (2) 2008: 39-50


Relaxing $\ell_0$ constraints in an optimization I have a feasibility question that can be framed as follows. I'm given a point $p$ in a $d$-dimensional vector space, and I want to find the closest point $q$ to $p$ that satisfies a set of "$\ell_0$ constraints" of the form

  Given a set $S \in [1\ldots d]$, at
  most one of $\{q_j, j \in S\}$ can be
  nonzero.

The notion of closeness varies, but for now it is sufficient to assume a convenient distance like $\ell_2^2$.

Are there any known relaxations to linear constraints that are "good" in the sense of providing a "close enough" polytope to approximate the original constraints, where I'm also pretty flexible on the definition of "close enough"

I am not sure if I understand the problem correctly, but as is written, the problem seems to admit several simplifications, and in particular the problem in the ℓ22 case is equivalent to the minimum-weight vertex cover if I am not mistaken.

Without loss of generality we can assume that |S|=2 in every constraint, because a constraint with |S|>2 is equivalent to the set of constraints where S runs over all pair of elements in the original set S.  Therefore, the ℓ0 constraints can be visualized as a graph G with d vertices.  Using the graph G, the constraints can be restated as follows: the set of the vertices corresponding to the coordinates i with qi=0 must be a vertex cover of G.
Assume that the distance is defined by ℓ22 or some norm.  In this case, any point q can be transformed to a point q′ that satisfies for every i, q′i∈{0,pi}, simply by setting $$ q'_i = \begin{cases} p_i, & q_i \ne 0, \\ 0, & q_i = 0, \end{cases} $$ and this transformation never increases the distance from the point p.  In particular, if the distance is the sum of coordinate-wise distance (as in the case of the ℓ22 distance), the problem is exactly the same as the minimum-weight vertex cover.

As for an LP relaxation of the vertex cover problem, a quick search leads to e.g. the lecture notes (Lecture 9) by Uriel Feige.


Provable statements about genetic algorithms Genetic algorithms don't get much traction in the world of theory, but they are a reasonably well-used metaheuristic method (by metaheuristic I mean a technique that applies generically across many problems, like annealing, gradient descent, and the like). In fact, a GA-like technique is quite effective for Euclidean TSP in practice.

Some metaheuristics are reasonably well studied theoretically: there's work on local search, and annealing. We have a pretty good sense of how alternating optimization (like k-means) works. But as far as I know, there's nothing really useful known about genetic algorithms.

Is there any solid algorithmic/complexity theory about the behavior of genetic algorithms, in any way, shape or form ?  While I've heard of things like schema theory, I'd exclude it from discussion based on my current understanding of the area for not being particularly algorithmic (but I might be mistaken here).

Y. Rabinovich, A. Wigderson. Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999. (Also available from Avi Wigderson's home page)


Decide whether a point is a vertex of a polytope? Inspired by the question, I would like to ask the following question:

Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection
$f(\Theta)= \{(\vec{c}_1\cdot \vec{x}+ d_1, \cdots, \vec{c}_m\cdot \vec{x}+d_m)\mid A\vec{x}\leq b\}$, a point $\vec{y}\in \mathbf{Q}^m$

Decide whether $\vec{y}$ is a vertex of $f(\Theta)$, what's the complexity?

I strongly believe there is a polynomial time (one might obtain many $\vec{x}$'s which project to the given $\vec{y}$ and check one of these $\vec{x}$'s is a vertex of $\Theta$?). However, I do not have a clear algorithm.

This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ could be given by a separation oracle, rather than explicitly, and it is also possible to solve an appropriately formulated version for a polyhedron.

Observe first that we have an efficient separation oracle for $P = f(\Theta) = C\Theta + d$. Indeed, deciding $y \in P$ amounts to solving the feasibility problem
$$
y = Cx\\
Ax \le b
$$
over the variables $x$. This problem can be solved with the usual techniques, e.g. the ellipsoid method. By the equivalence of separation and optimization, we can also solve arbitrary linear optimization problems over $P$.

Let us first assume $y \in P$: otherwise we are done. Then, by Caratheodory's theorem, $y$ can be written as a convex combination of at most $m+1$ vertices of $P$. Moreover, such a convex combination is computable in polynomial time using a separation/optimization oracle for $P$: this is proved, for example, in Corollary 14.1g of Schrijver's Theory of Linear and Integer Programming. I.e., given an efficient separation oracle for $P$, we can construct a procedure that takes $y$ and returns vertices $v_1, \ldots, v_k$ of $P$, $k \le m+1$, and coefficients, $\lambda_1, \ldots, \lambda_k \in (0,1]$ such that $y = \sum_{i = 1}^k{\lambda_i v_i}$. Then, $y$ is a vertex of $P$ if and only if the procedure returns $v_1 = y$ and $\lambda_1 = 1$. It is clear that if this happens, $y$ is a vertex. Conversely, if this does not happen, then $y$ can be written as a convex combination of other points in $P$, which means that $y$ is not extremal, and, therefore, not a vertex.

Computing $v_1, \ldots, v_k$ and $\lambda_1, \ldots, \lambda_k$ using a separation/optimization oracle is not too hard. First you compute a vertex $u_1$ of $P$: figuring out  how to do this by optimizing over $P$ is a nice exercise. If $u_1 = y$, we are done. Otherwise, let $\ell$ be the half-line starting at $u_1$ and going through $y$, and let $z$ be the point where $\ell$ intersects the boundary of $P$. Then $z$ lies in a proper face of $P$, and we can recurse on that face to express $z$ as a convex combination of the vertices of the face. We finish by expressing $y$ as a convex combination of $z$ and $u_1$. See Schrijver's book for the details.


Implication of Exponential Time Hypothesis falseness? The proof that Exponential Time Hypothesis (ETH) is true, would imply that P!=NP among other implications (like solvability of SAT in sub-exponential time is not possible in the worst case).

But, if proven that ETH is false, how would it impact the Complexity Hierarchy and what would be the implications of the proof. Results, that immediately follow from the ETH falseness (based on our current knowledge)?

One such result is by Megiddo and Vishkin. They proved that minimum dominating set in tournaments is in $QP$. Additionally, they showed that tournament dominating set has P-time algorithm if and only if SAT has subexponential time algorithm. Therefore, ETH falseness implies that tournament dominating set is in $P$ which seems unlikely.


What are some efficient algorithms for determining if a quadratic multivariate polynomial has a solution? I know that in general, multivariate polynomial satisfiability is equivalent to 3-SAT; however, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a polynomial time solution.

I guess the more general question would be, are there any classes of multivariate polynomials for which the satisfiability problem is efficiently solvable?

You can decide if a quadratic polynomial $p: \mathbb{R}^n \rightarrow \mathbb{R}$ has real roots with some linear algebra. As you note, the general case should be hard.

Observe first that $p(x) \neq 0$ for all $x \in \mathbb{R}^n$ if either $p(x) > 0$ or $p(x) < 0$ for all $x$ (this follows by continuity). So it is enough to be able to decide if $p(x) > 0$ for all $x$. In general this is related to complexity-theoretic versions of Hilbert's 17th problem: a polynomial $p(x)$ is positive over the reals if and only if you can write $p$ as the sum of squares of rational functions and a positive constant $c$ (this is a theorem by Artin). Finding this decomposition or solving the decision problem is most likely hard in general, but the quadratic case is easy, because of the magic of the spectral theorem. For more information about the general case, look at Devanur,Lipton,Vishnoi, and Monique Laurent's survey.

Let us write $p(x) = p_2(x) + p_1(x) + c$ where $p_2$ is homogeneous of degree 2, $p_1$ is linear, and $c$ is a constant. Let us define $q(x_0,x) = p_2(x) + x_0p_1(x) + cx_0^2$ to be the homogenization of $p$, where $x_0$ is an additional variable.

Claim. $p(x) > 0 \Leftrightarrow \forall x_0 \neq 0: q(x_0,x) > 0$

The "if" direction is easy. In the non-trivial direction, assume $p(x) > 0$ for all $x$ and assume $x_0 \neq 0$:
$$
q(x_0,x) = x_0^2q\left(1,\frac{x}{x_0}\right) = x_0^2 p\left(\frac{x}{x_0}\right) > 0.
$$
QED

Notice also that, because $q(x_0, x)$ is continuous, if $p(x) > 0$ for all $x$ then $q(x_0,x) \geq 0$ for all $(x_0,x)$ (including $x_0 = 0$).

Since $q$ is homogeneous, we can write $q(x_0,x) = y^TQy$, where $Q$ is a symmetric matrix and $y = (x_0,x)$. By the above, if $p(x) > 0$ for all $x$, then $Q$ is positive semidefinite. Moreover, $q(x_0, x) > 0$ for all $x_0 \neq 0$ if and only if the kernel of $Q$ is a subset of the hyperplane $\{y = (0,x): x \in \mathbb{R}^n\}$. Both these conditions can be decided in polynomial time by computing the SVD of $Q$.


Consensus on P = NP in a world where RP = NP $RP = NP$ is widely conjectured to be false.

But imagine for a moment that it is true. In such case, how likely would be that $P = NP$?

Put in other words: in a world where $RP = NP$, what might still be seen as an obstacle for us to believe $P = NP$?

Honestly speaking, I do not think that Stack Exchange is a suitable place to ask for a future prediction.  Despite this, I will post a response because it is fun to play with the idea of fortune telling.

As far as I know, the possibility of P≠RP=NP has not been ruled out.  Moreover, there is a language A such that RPA=EXPA [Hel83, Kur83], which immediately implies that PA≠RPA=NPA.  (I have not checked [Hel83] or [Kur83], and I took the result and the references from the remark after Theorem 6 in [Hel86].)  In other words, even proving the implication RP=NP ⇒ P=NP requires a nonrelativizing technique, and therefore it is understandable that this implication has not been proved.

(Lance Fortnow has discussed a similar result in the Computational Complexity blog: Oracle Results are Good For You.)

Now let’s turn to the fortune-telling part.

How much does this oracle result tell about the likeliness of P=NP in the world where RP=NP has been already proved?  Not much.  At the very least, it should not be taken as evidence that in the world where RP=NP has been proved, it is still likely to be difficult to prove P=NP.  In such a world, some new, powerful nonrelativizing techniques are known to human, and therefore it would not be reasonable to interpret “requires a nonrelativizing technique” as evidence for difficulty.

Speaking more broadly, if RP=NP has been proved despite all the beliefs (and also proof technique barriers) against it, then our current intuitive understanding about efficient computation is likely to be very wrong.  Obviously we cannot apply our current intuition to reason about the world where our current intuition fails spectacularly.  I do not think that we can make an educated guess about such a world except for what has been rigorously proved.

References

[Hel83] Hans Heller.  On relativized polynomial hierarchies extending to two levels.  In Proceedings of Conference on Computational Complexity Theory, pp. 109–114, UC Santa Barbara, March 1983.

[Hel86] Hans Heller.  On relativized exponential and probabilistic complexity classes.  Information and Control, 71(3):231–243, Dec. 1986.  DOI: 10.1016/S0019-9958(86)80012-2.

[Kur83] S. Kurtz (Stuart A. Kurtz?).  The fine structure of NP: Relativizations.  In Proceedings of Conference on Computational Complexity Theory, pp. 42–50, UC Santa Barbara, March 1983.


Equivalent formula for LTL with and without past operators I have recently been researching LTL with and without past operators.
From my understanding, both LTL and PLTL (LTL with Past) are equally expressive, however, PLTL is exponentially more succinct.

I have been searching for a list abbreviations between LTL and PLTL formulae but have found nothing, and I cant seem to figure them out myself.

If LTL allows the formulae

$\bigcirc\phi$ for  $\phi$ is true at the next moment in time,
$\Diamond\phi$ for  $\phi$ is true some time in the future,
$\Box\phi$ for  $\phi$ is true always in the future, and
$\phi\mathcal{U}\psi$ for  $\phi$ is true until $\psi$ is true,

and PLTL allows the additional formulae using the past versions of the temporal operators:

$\bigcirc^-\phi$ for  $\phi$ was true at the previous moment in time,
$\Diamond^-\phi$ for  $\phi$ was true some time in the past,
$\Box^-\phi$ for  $\phi$ was true always in the past,
$\phi\mathcal{S}\psi$ for  $\phi$ has been true since $\psi$ was true in the past,

then how are 1-4 expressed using only LTL?

The "equally expressive" statement means that if a formula of PLTL is a statement about the future, i.e. if it's evaluated at the first instant $0$ of the time domain $\mathbb N$, then there exists an equivalent LTL formula.
This means that nesting future and past operators is not more expressive than nesting just future operators, as long as the global meaning of the whole formula is solely about the future.

Here are some examples of this equivalence:

$\lozenge\square\lozenge^-\varphi\equiv\lozenge\varphi$
$\lozenge(\alpha\wedge (\varphi \mathcal S \psi)) \equiv \lozenge (\psi \wedge (\alpha\vee \bigcirc (\varphi \mathcal U (\varphi\wedge \alpha)))$


Testing for equality with zero error This question comes from what I asked in a comment here, although I realized that
I don't actually care about which input is less than the other, if they're different.

Alice and Bob have n-bit strings, and want to figure out if they're equal
while doing little communication. $\:$ They can use a randomized solution,
but there must be zero chance of getting the wrong answer.

Parametrized by $n$, how much communication is needed to for a protocol that:

outputs one of {NO,MAYBE,YES}
for all input pairs, the probability of the protocol outputting MAYBE on that pair is at most 1/2
the protocol never outputs YES on unequal inputs, and never outputs NO on equal inputs
?

Since this falls between the deterministic and the standard randomized cases,
the bounds for those are upper and lower bounds, respectively, for this question.

Let $D$ be the distribution on inputs that w.p. $p = 1/(1+\epsilon)$ picks $(x,x)$ for random $x$, and w.p. $1-p$ picks $(x,y)$ for random $x \neq y$. An appropriate choice of random coins leads to a deterministic protocol that never makes mistakes and outputs MAYBE w.p. at most $1/2$ with respect to $D$. In particular, it must answer YES on at least $1-(1/2)/p = 1/2 - \epsilon/2$ of the nodes $(x,x)$.

Suppose that the protocol uses $C$ bits of communications. It therefore has at most $2^C$ leaves. Each leaf is a monochromatic combinatorial rectangle, and so each of the at least $(1-\epsilon) 2^{n-1}$ YES answers must end up in a different leaf. We conclude that $C \geq n-1$.


Zero knowledge proof for value of a hash function Is there a zero knowledge proof which demonstrates that Peggy knows a value v whose hash-function is w?

In my understanding of the general theorems on zero-k there EXISTS such a function if the has-function has polynomial time complexity. However, I would like to know how such the protocol would look like for the case of SHA-256. My problem is, that the usual proof requires me to reduce the fact of having a certain SHA-256 to Graph 3 Coloring, for example, and I do not see how this could be done practically.

In the rump session of Crypto 98, Hal Finney provided a talk which might be of your interest. The title is "A zero-knowledge proof of possession of a pre-image of a SHA-1 hash." I have not found any transcripts., but the video is available on both YouTube and Google Videos. (the videos are no longer available; see the comments below.) The video is now available from my Google Drive.


Recursively presenting or even enumerating all P-hard languages A class of languages $C$ is recursively presentable if there is an effective enumeration of Turing machines $\mathcal{M}_1,\mathcal{M}_2,\ldots$ such that $C=\{L(\mathcal{M}_i)\mid i=1,2,\ldots\}$. Uwe Schöning considers this notion in his elegant generalisation of Ladner's theorem ("A Uniform Approach to Obtain Diagonal Sets in Complexity Classes", Theor. Comp. Sci. 18, 1982).

In a previous answer on this site, Ryan Williams argues that the set of all P-hard languages can be recursively presented "similar to how Schoening does it for the NP-hard sets". I would like to know how this works, since I cannot find this in the paper. Schöning works with Turing reductions and shows that the NP-complete sets are recursively presentable. We can adapt his argument to NP-complete sets under polynomial many-one reductions as follows:

Take an enumeration $(\mathcal{M}_i,\mathcal{R}_i)_{i\geq 1}$ of pairs of polynomially time-bounded non-deterministic Turing machines $\mathcal{M}_i$ and polynomial reductions $\mathcal{R}_i$ (we can enumerate polytime machines and reductions by enumerating all machines and polynomials, and augmenting them with a polytime "stop clock" that enforces timely halting).
For each pair of a machine $\mathcal{M}_i$ and reduction $\mathcal{R}_i$, the let $\mathcal{M}'_i$ denote a machine that does the following on input word $w$:

For all input words $v$ with $|v|<|w|$, test whether $\mathrm{SAT}(v)=\mathcal{M}_i(\mathcal{R}_i(v))$, i.e., whether $\mathcal{R}_i$ reduces $\mathrm{SAT}$ to $L(\mathcal{M}_i)$ on these instances.
If yes, accept iff $\mathcal{M}_i$ accepts $w$
If no, accept iff $w\in\mathrm{SAT}$

The required enumeration is $\mathcal{M}'_1,\mathcal{M}'_2,\ldots$, since each of those either decides $\mathrm{SAT}$ (up to finitely many cases) or some other language in NP to which $\mathrm{SAT}$ can truly be reduced.

I do not see how to apply this idea to recursively present all P-hard languages. One could readily recursively present, e.g., all P-hard languages in ExpTime (which would suffice as an answer in the other thread), but I don't see why the P-hard languages in general (including undecidable ones) should even be countable.

After some further thought, partly triggered by writing a long question, it seems clear that the set of P-hard languages is not countable, and therefore not recursively presentable either.

To see why, consider languages $L$ that satisfy $w\in 2SAT$ iff $ww\in L$. 2SAT can be log-space reduced to any such language by definition. However, there are countably many words that do not have the form $ww$, and the languages might differ on their membership status. Hence we obtain uncountably many P-hard languages of this form.

Moreover, it does not seem possible to recursively present all decidable P-hard languages either, since there is no effective enumeration of all Turing machines that are guaranteed to halt (this seems to be the minimal requirement for applying Schöning's construction).


Pumping Lemma over 2 way Automaton Pumping Lemma essentially implies that for a NFA $N$ having $N_0$ states over a unary language $L_0$ any string belonging to $L_0$ can be obtained by 'pumping' one of the strings that have a length smaller than $N_0$. Thus, a string smaller than $N_0$ that is accepted by $N$ always exists.

Now, since a 2 Way unary NFA also accepts a regular language, for any 2 way unary NFA $M$ having $M_0$ states over a unary language $L_1$ can we state the same regarding smallest accepted string length (using the same pumping lemma) as above w.r.t. $M_0$?

I believe the answer is true, but please confirm?

The exact definition of acceptance we are using is the same as provided in the classic (Hopcroft and Ullman - Formal Languages and their relation to Automata, Section 3.7 - Two-Way Finite Automata):

"A two-way finite automaton will start in state q0 with its input head scanning the leftmost cell on the input tape. Should M ever move off either end of input word x, M halts. An input word will be accepted by M if and only if M eventually moves off the right end of x at the same time it enters a final state.

M can reject a word x by:

1. moving off the left end of x.

2. moving off the right end of x in a nonfinal state.

3. looping."

Claim: If $M$ is a 2-way NFA (without endmarkers) with $n$ states
which acceptes a unary language $L\not=\emptyset$ then there is a word $w \in L$ of
length at most $3n+5$.

Proof sketch:
Let $v\in L$ be some word of some length $N>3n+5$ and let $\rho$ be
an accepting run for $v$. Let $v=v_1 v_2$, where $v_2$ is the suffix
of $v$ of length $n+1$. Let $\rho=\rho_1\rho_2$, where $\rho_1$ is
the prefix of $\rho$ that ends when the head moves from the last
position of $v_1$ to the right, for the last time. Let $q$ be the last
state of $\rho_1$.

Before we manipulate $\rho_1$, we first prepare a "way out" for $M$ by
showing that we can pump up (!) $\rho_2$.

For each of the $n+1$ positions $i$ of $v_2$ let $p_i$ be the first
state in which this position is visited in $\rho_2$. Clearly, there
must be positions $i<j$ with $p_i=p_j$ and thus we can pump up
$\rho_2$ by strings whose length are multiples of $j-i$, if we like. (This will not affect
$\rho_1$ and the subrun $\rho'_1$ that will be described below).

However, the main part of the construction is to transform $\rho_1$
into a subrun $\rho'_1$ on the string $u$ of length $2n+3$. The idea is to
center $\rho'_1$ around position $n+2$ and neither let it get to
position 1 nor to position $2n+3$. The construction will make sure
that $\rho'_1$ ends in state $q$ at some position (between 2 and 2n+2). It
can then be completed to an accepting run by adding a suitably pumped
version of $\rho_2$ that makes sure that the overall string $uv'_2$
has length at least $2n+2$ (but at most $3n+4$).

Let $\rho_0$ be the prefix of $\rho_1$ until position $n+2$ is reached
for the first time. The prefix of $\rho_1'$ is then just $\rho_0$.

Let us assume that the next step of $M$ is to the left. We follow the next
steps of $\rho_1$ until either it comes back to position $n+2$ or
until it attempts to step at position 1. If the former happens, this
part of $\rho_1$ is just copied to $\rho'_1$. In the latter case, we
consider for each position $1,\ldots,n-1$ the state $r_i$ in which it
is visited for the first time in the current subrun. Clearly, there must
be $i<j$ with $r_i=r_j$ and we just remove the part of the subrun between
$(j,r_j)$ and $(i,r_i)$. The consideration of the thus shortened run
goes on in this way until position $n+2$ is reached again.

When $M$ moves to the right of $n+2$, a similar procedure is applied with
positions $n+3,\ldots,2n+3$ in place of $1,\ldots,n+1$.

It is easy to see (but a bit tedious to formally denote) that the resulting subrun
$\rho'_1$ is valid for $M$, remains in the interval $[2,\ldots,2n+2]$
and eventually reaches state $q$ at some position $k$. It is then
extended to an accepting run as described above.


Does Hadwiger conjecture imply that NP = coNP? (Disclaimer: I suspect the answer is no, but I fail to see why)

Here is a nice picture by David Epstein (taken from Wikipedia) illustrating Hadwiger's conjecture:

The point is that if in a given graph $G$ some-one gives you four connected subgraphs $G_1$, $G_2$, $G_3$, $G_4$ (here illustrated with grey boxes) such that for each of the six combinations $(i, j)$ there is at least one edge in $G$ connecting a vertex in $G_i$ to one in $G_j$, then the conjecture claims that there is no 3-coloring of the big graph $G$.

Suppose that Hadwiger's conjecture is true. Wouldn't this put 3-coloring in coNP? At least to me it seems that once someone gives you $G_1, G_2, G_3, G_4$ their connectedness and existence of 6 edges connecting the four subgraphs can be checked in time quadratic in the number of vertices of the big graph $G$.

But if indeed 3-coloring is in coNP, wouldn't that put all of NP in coNP thus making these complexity classes equal?

This seems wrong, my impression was that both Hadwiger's conjecture and $NP \neq coNP$ are widely believed, so most likely something is wrong with my reasoning above.

But what?

I think the problem here is that you are stating the converse of Hadwiger's conjecture. The conjecture (according to Wikipedia) states that "if a graph needs at least k colors for a proper coloring, then it contains a $K_k$ minor (i.e. there exist subgraphs $G_1,\ldots,G_k$ as you state)". You are talking about the assertion that "If a graph has a $K_k$ minor, then it needs at least k colors for a proper coloring".

These two are not equivalent. Indeed, the latter statement is false. Consider for example a $K_{n,n}$. This graph contains a $K_n$ minor (take a perfect matching, this gives a collection of $n$ connected components all of which have edges to each other). However, its chromatic number is 2.


What are some algorithms where space complexity tends to be the limiting factor in practice? Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? It puts a hard upper bound on what you can do, whereas time is only a factor if you're 'impatient.'
Preferably something practical.

Most computations in algebraic geometry / commutative algebra.
Most involve computing Grobner bases, which are EXPSPACE-hard in general. There are some parameter regimes where this improves and thus some computations can reasonably be done in practice (e.g. using Macaulay2 or SINGULAR), but very often it quickly eats up all the space and crashes.  I think one of the first papers to look at this was Bayer & Mumford "What can be computed in algebraic geometry?".
(FWIW, my recent experience with these programs has been that there is a trichotomy: either the answer returns in (1) seconds, (2) a few minutes, or (3) so long that you give up / so much memory that it crashes.)


Best known algorithm for a common problem. I am looking for the best known algorithm for the following problem:
Input: Matrix M with R rows and C cols and values true-false in each position
Output: Minimum number of cols such that the OR operation between all selected cols results in R trues.

I think another form of this problem is: Given C numbers of N bits, get the minimum amount of numbers needed to sum 2^N - 1.

In case this is NP-Complete, then does someone know where can I find the reduction? And is there any pseudo-polynomial algorithm? Maybe using dynamic programming on some bounded variable?

Thanks in advance.

This is the set cover problem.

The universe $\mathcal{U}$ corresponds to the rows of the matrix $M$, and each member of $\mathcal{S}$ corresponds to each column. The entry $m_{i,j}$ is true if and only if the $i$-th element of $\mathcal{U}$ belongs to the $j$-th member of $\mathcal{S}$.


Is this game EXPSPACE-complete? Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be some string.

Consider the following Alice and Bob game. Initially, Alice and Bob have $m_A$ and $m_B$ dollars respectively. Alice wants $M^A(x)=1$ and Bob wants $M^A(x)=0$.

At every step of the game a player can add one string to $A$; this costs one dollar. Also a player can miss his or her step.

The play ends if both players spends all money or if some player missed step when he or she in a losing position (that defines by the current value of $M^A(x)$).

Question: is the problem of defining the winner of this game for given $M, x, m_A, m_B$ is an

EXPSPACE-complete task?

Note that $M$ can ask (for belonging to $A$) only strings of polynomial length so there is no  sense for Alice or Bob to add more longer strings to $A$. Hence, this problem is in EXPSPACE.

I don't have an exact characterization but it's unlikely this problem is EXPSPACE-complete. Suppose $M^{\Sigma^*}(x)$ accepts and let $S$ be the polynomial-size set of strings queries by this machine. If I understand the game right, Alice can win by playing every string in $S$. The only way to prevent this is if $m_A$ is polynomially-bounded but that would put the game somewhere inside the exponential-time hierarchy (or lower).


NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the size of every part is the same, i.e., $k$. The goal is to maxmize the sum of the shared neighbors of every part, which can be difined as:
\begin{gather}
    \sum_{i=1}^m SN_{i}\\
    s.t. \quad\qquad SN_{i} = \cap_{v_i \in P_i} Nei(v_i)\\
    |P_i| = k\\
    \qquad \sum_{i=1}^m |P_i| = nk
\end{gather}

where $SN_{i}$ is the shared neighbours of the nodes in part $P_i$. For convenience, we regard that the node is the neighbour of itself.

I think the problem is np-hard. In my view, we can construct a specific graph which contains n k-clique. We then think about it as a clique-cover problem. However, I think the solution is a little strange... How should we prove it?

Thanks in advance!!!

You can notice that $SN_i$ is maximum if $P_i$ is a clique of size $|P_i|$.

So the decision version of your problem is very similar to the CLIQUE PARTITION PROBLEM which is NP-complete, the only difference is that you require that all parts $P_i$ have the same size.

But the problem of partitioning a graph into 3 cliques of the same size is still NP-complete.

Indeed 3-COLORING remains NP-complete even if we require that all color classes have the same size (I'll call it EQUAL SIZE 3-COLORING). A quick proof idea is: given $G$ make 3 copies of it $G_1, G_2, G_3$, pick the same node $v$ in each copy of $G$: ($v_1, v_2, v_3 $) and "link" them to form a clique $K_3$. $G$ is 3 colorable if and only if $G' = G_1 \cup G_2 \cup G_3 \cup K_3$ is 3 colorable with equal size color classes.

But EQUAL SIZE 3-COLORING a graph $G$ with $3n$ nodes is equivalent to find 3 cliques of size $n$ in its dual $\bar G$. Which is also equivalent to partition $\bar G$ into 3 parts with a total sum $\sum SN_i = 3n$


Quantum complexity of TQBF There is no classical algorithm for $n$-bit TQBF with better than $O(2^n)$ complexity.  Is that also the best known bound for quantum algorithms / circuits?
Edit: As pointed out by Huck Bennett, in the full alternation subset of TQBF we can in fact beat $O(2^n)$ via randomized tree search.  This is the case I care about most, so I would also be curious for the best exponent for a quantum algorithm if there are all $n-1$ quantifier flips.

The best quantum algorithm for QBF on n variable formulas of size s runs in about $2^{n/2}poly(s)$ steps, regardless of quantifier alternations. This is due to a series of advances on quantum algorithms for game tree search in the early 2000s.
Here is the first reference I found from googling; there are more: https://arxiv.org/abs/0907.1623


Why isn't the Charikar algorithm for finding the densest subgraph optimal? I read about the algorithm in
Greedy Approximation Algorithms for Finding
Dense Components in a Graph by
Moses Charikar,
and I tried to find an instance/graph where the algorithm returns a different solution from the optimal one but I didn't succeed.
Can anyone provide me an example where the algorithm 'fails' and proves that the approximation is no less than 2?

Suppose you have a complete graph on four nodes and then next to it a graph with five nodes comprising a degree four hub and four degree 3 satellites. The greedy algorithm might start by removing one of the satellites and thus spoil the optimum which is 1.6

o-------o    o-------o
| \   / |    | \   / |
|   X   |    |   o   |
| /   \ |    | /   \ |
o-------o    o-------o

For the sake of completeness: given a graph $G=(V,E)$ the task is to find a subset $S\subseteq V$ maximising the quantity $|E(S)| / |S|$ where $E(S)\subseteq E$ is the set of edges with endpoints in $S$. The greedy algorithm operates by successively removing vertices of minimal degree and then searching for the optimal $S$ among the successively shrinking set of remaining vertices.


generate a graph with fixed min cut Is there a constructive way to generate a graph with a fixed min cut equal to $k$?
One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to get the desired min cut -- but I am wondering if there is a more systematic procedure?

Ideally I would want to generate a random instance of a graph with min-cut=$k$, and I would want it to be bipartite, but insight on any part of this question would be helpful!

Thanks in advance!

In his 1962 paper "The Maximum Connectivity of a Graph", Harary describes a way to construct for integers $p$ and $q$ with $q\ge p-1$ a way to construct a graph with $p$ vertices and $q$ edges  that is $k=\lfloor 2q/p\rfloor$-connected. Roughly, the idea is to give indices from $0$ to $p-1$ to the $p$ vertices and then add edges between vertices whose indices (modulo $p$) differ by at most $k/2$ (the exact construction depends on whether or not $2q/p$ is an integer).

One could start with these graphs and then perturb them by adding and removing edges without changing the connectivity. The graphs will not be bipartite, however.

Another easy way of creating random graphs with a certain edge-connectivity value is to exploit those cases in which edge-connectivity and minimum degree are identical since creating random graphs with a fixed minimum degree is much easier. Such conditions, also for bipartite graphs, are discussed for example in the paper On equality of edge-connectivity and minimum degree of a graph by Plesník and Znám.


Color shifting in a bipartite graph Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the degree of each vertex is at most $k$. Now consider the problem of coloring $G$'s edges with $k$ colors, such that no adjacent edges have the same color. This problem can be solved efficiently by noting that $G$ is a subgraph of a $k$-regular bipartite graph and thus one can compute a perfect matchings to color $G$.

The problem I'm trying to solve is as follows. Assume that we have colored $G_1$ and now we're given a new graph $G_2$ with the same properties and vertices of $G_1$ but with possibly different edges. We want to color $G_2$ while trying to save as many colors from $G_1$ as possible. That is, if there is an edge $e_1$ of $G_1$ that is also present in $G_2$, then we prefer to keep its color from the previous coloring of $G_1$.

Formally, suppose $c_1$ is a coloring of $G_1$ and $c_2$ is a coloring of $G_2$. Define a function $f_{c_2}$ from the edges of $G_2$ to $\{0, 1\}$ as follows: $f_{c_2}(e) = 1$ iff $e$ is present in both $G_1$ and $G_2$ and $c_1(e_1) = c_2(e_2)$. Now the problem can be stated as follows. Given $G_1$, a coloring $c_1$ of $G_1$ and given $G_2 = \langle V_2, E_2\rangle $, we're asked to compute a coloring $c_2$ of $G_2$ such that $\sum_{e \in E_2}f_{c_2}(e)$ is maximized.

My approaches:

I tried to use the Hungarian algorithm $k$ times to find $k$ perfect matchings. Lets say i want to save as many blue colored edges as possible, so i give those edges in $G_2$ a high weight, i find a perfect matching to color it with blue and then i proceed to the next color. The problem with this solution is that the order of the colors that we choose may affect the outcome.
I thought that maybe one can state the problem as an instance of LP (linear programming).

A help would be appreciated,

The precoloring extension problem is the following:

Input: a number $k$ and a graph $G$ some of whose edges are labeled with labels in $\{1, 2, \ldots, k\}$.

Decision: is it possible to color the edges of $G$ with colors $1, 2, \ldots, k$ such that no adjacent edges share a color and such that each initially labeled edge is colored with the color it is labeled with.

In other words, given a partially colored graph, can you finish coloring it using only $k$ colors?

A specific case of this problem was proven NP-hard in the paper "NP‐completeness of list coloring and precoloring extension on the edges of planar graphs" by Daniel Marx. In particular, the author showed that precoloring extension is NP-hard even when $k = 3$ and $G$ is a planar 3-regular bipartite graph.

As it turns out, this means your problem is NP-hard too. Here's a simple reduction:

Given an instance of the precoloring extension problem consisting of partially colored planar 3-regular bipartite graph $G$ and $k = 3$, we build an instance of your problem:

We set the degree bound/number of colors (which you called $k$) to be $3$
We set $G_1$ to be $G$ with all initially non-colored edges removed
We set $c_1$ to be the partial coloring of $G$ (and since $G_1$ consists of the edges of $G$ that are colored, $c_1$ is a coloring of $G_1$)
We set $G_2$ to be $G$

Notice that $G_1$ and $G_2$ are both bipartite graphs with vertex-degrees at most $3$.

It is possible to color $G_2$ with a coloring $c_2$ that matches $c_1$ everywhere if and only if it is possible to extend the partial coloring $c_1$ on $G_1$ to a full coloring of $G_2 = G$. In other words, finding a coloring for $c_2$ which differs from $c_1$ as little as possible is equivalent to extending the partial coloring of $G$ into a full coloring.

Thus, your problem is NP-hard.

If you need to solve instances efficiently despite the fact that your problem is NP-hard, I recommend using an ILP solver: for each edge-color pair in $G_2$, make a variable that is 1 if the edge has that color and zero otherwise; then use inequality constraints to enforce that the number of colors of each edge is exactly 1 and that the number of edges at each vertex of each color is at most 1; finally, set the objective that the solver tries to maximize to the sum of the variables corresponding with edge-color pairs present in $G_1$.


Polynomial Time Algorithm for Graph Isomorphism Testing "Michael I. Troﬁmov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs.

The paper is given in arXiv. The companion website gives a proof-of-concept program which runs the algorithm. (The password for the program is given in the paper.)

I wanted to know whether the community is aware of Troﬁmov's results, and whether it's been proved, refuted, or unresolved?

For some more discussion of this particular paper, see this thread on a related Wikipedia talk page. Some of the participants in that discussion found specific bugs, and the paper does not seem to have been updated in response. I tried to read it myself but rather than finding any specific bugs I just got lost in vague descriptions of matrices and matrix manipulations that did not make clear which variables were inputs and which were outputs. Based on that experience I don't think the paper should be taken seriously until it's passed some level of peer review (accepted to one of the usual journals or conferences).

More generally, it is easy to define algorithms for graph isomorphism that attempt to amplify some sort of subtle asymmetry in the graph to the point where it is obvious how to match the vertices to each other, and it is hard to find counterexamples for these algorithms, but that is very difficult from having a clear proof of correctness that works for all graphs.


Fast extraction of the edges of an induced subgraph Let $G = (V, E)$ be an arbitrary undirected graph and $W \subseteq V$ a subset of its vertices. What is the complexity of the best algorithms for obtaining the edges $F$ of the induced subgraph $H = (W, F)$?

We can iterate over all the pairs of vertices taken from $W$ and test whether they're in $E$ using a hash table. This has a complexity of $O(|W|^2)$.

Another algorithm is to iterate over all the neighbors of all the vertices in $W$, and keep the pairs that are in $W\times W$. If the average number of neighbors is $d$, the complexity of this algorithm is $O(|W|d)$.

Can we do better than either $O(|W|^2)$ or $O(|W|d)$?

I'm assuming you can do some preprocessing to organize your graph for this computation, since otherwise your question makes little sense.

In the $O(|W|d)$ algorithm, you can replace the average degree by the degeneracy of $G$. For an undirected graph $G$, being $d$-degenerate means there is a vertex ordering such that each vertex has at most $d$ neighbors that are later in the ordering. To extract the induced subgraph, loop over each vertex of $W$ and test, for each of its $\le d$ later neighbors in a degeneracy ordering, whether that neighbor also belongs to $W$. Each edge is extracted once, when the loop reaches its earlier endpoint.

Because it tests a subset of the same pairs, this algorithm is never worse than your average degree algorithm and could in some cases be significantly better. And if you're computing worst case bounds in terms of the numbers of vertices and edges of the original graph, the average-degree algorithm can be as bad as $\Theta(|W|n)$ (if $W$ picks out vertices of unusually high degree), even for sparse graphs, while the degeneracy algorithm is always $O(|W|\sqrt m)$ (because degeneracy is always $O(\sqrt m)$).


When can partial spectral sparsifiers be combined? A few important papers about spectral sparsifiers and friends contain a technical idea that involves building many different sparsifiers that each "partially" solve the problem, and then combining them at the end.  To give two examples:

The original paper by Spielman and Teng works roughly by partitioning the graph into parts of good expansion and $\le |E|/2$ edges going between the parts, then building a sparsifier of each part, and then recursing on the "remainder" graph to depth $\log n$ to get the rest.  Implicitly, one then combines these partial solutions at the end for a full solution.
This paper by Jambulapati and Sidford builds spectral sketches, which are data structures (not subgraphs) that can approximate Laplacian quadratic forms $x^T L x$ with probability $\ge 2/3$ for any given $x$.  As they mention, one can easily amplify this probability to $p$ by computing $\log (1/p)$ sketches and taking their median.  This critically uses that they sketch with data structures, not graphs, and it raises the question of whether a similar probability amplification is possible for subgraphs with this property.

Formalizing the question, let $G = (V, E, w)$ be a graph and let $H_1, H_2$ be reweighted subgraphs such that, for some $X_1, X_2 \subseteq \mathbb{R}^n$ we have
$$x^T L_{H_i} x \in (1 \pm \varepsilon) x^T L_G x \qquad \text{for all } x \in X_i.$$

  I imagine that this does not imply generally that one can reweight $H_1 \cup H_2$ so that the above equation holds for all $x \in X_1 \cup X_2$.
  Is this accurate, and is there a nice example that demonstrates this?
  Are there natural additional assumptions we can make about $G, H_1, H_2$ so that this combination of $H_1, H_2$ does work in general, e.g. to enable recursive computation techniques like in the first paper?

Regarding your 1st question: no, this would not hold in general.

Rather (answering your 2nd question), the right way to interpret the approach by Spielman and Teng is as follows: let $G'$ be a vertex-induced subgraph of $G$, and $H'$ a spectral sparsifier of $G'$. Then the graph $G-G'+H'$ (replace all edges in $G'$ by those in $H'$) will be a spectral sparsifier of $G$. This easily follows by combining the Laplacians of $G$ and $H'$. As a result, we can sparsify $G$ by subsequently sparsifying subgraphs.

And finally, you are asking about ways to amplify the success probability of a sparsification algorithm. For spectral sparsification, there is a rather easy way: construct one with constant success probability, check whether it is indeed a spectral sparsifier (this amounts to checking whether a certain matrix is PSD, which can be done efficiently), if not, reiterate. After $O(\log(1/\epsilon))$ iteration this outputs a spectral sparsifier with probability at least $1-\epsilon$. Note that this cannot be done for say cut sparsification, as there is no efficient "verification procedure" to check whether a graph is a cut sparsifier of another graph.


What algorithm on a PRAM computes the connected components of a graph with least time complexity? The fastest method to compute the connected components of an undirected graph on a PRAM I have found is O(log n loglog n) in the 1993 paper Finding connected components in O(log n loglog n) time on the EREW PRAM, by K. Chong and T. Lam. Is there an algorithm with a smaller time complexity?

As Jeff suggested, I moved my comment to the answer section:

On the CRCW PRAM, achieving  $O(\log n)$ time is fairly easy (see J. v. Leeuwen, Handbook of TCS, Chapter 17).

On the EREW PRAM, Chong, Han and Lam (JACM, Vol 48(2), 2001) give an $O(\log n)$ algorithm for MST on an EREW PRAM. This should also solve the CC problem. Alternatively, use Reingold's logspace algorithm for undirected connectivity and standard simulation methods.


Existence of long induced paths in expander graphs Let's say that a graph family $\mathcal{F}$ has long induced paths if there is a constant $\epsilon > 0$ such that every graph $G$ in $\mathcal{F}$ contains an induced path on $|V(G)|^{\epsilon}$ vertices. I am interested in properties of graph families that ensure the existence of long induced paths. In particular, I am currently wondering whether constant-degree expanders have long induced paths. Here is what I know.

Random graphs with constant average degree (in the Erdős–Rényi model) have long (even linear-size) induced paths with high probability; see for example Suen's article.
Unique-neighbor expander graphs (as defined by Alon and Copalbo) have large induced trees. In fact, any maximal induced tree is large in such graphs.

Given these two facts I would expect that contant-degree expanders have long induced paths. However, I was unable to find any concrete results. Any insights are much appreciated.

The answer should be positive if your bounded-degree graph has both the property of having constant expansion and $\Omega( \log n)$ girth. The argument would be: start at a vertex, then for $n^\epsilon$ steps take a walk in which each step is chosen at random among those that don't take us back to where we were the step before. (So if the graph is $d$-regular we have $d-1$ random choices at each step.)

Now I claim that, for every $i$ and $j$, if I look at steps $i$ and $j$ of the walk, the probability that there is an edge between the vertex at step $i$ and the vertex at step $j$ is $n^{-\Omega(1)}$. Then, if $\epsilon$ is chosen sufficiently small, a union bound will show that the walk will induce a path with probability $1-o(1)$.

If $|i-j|$ is less then the girth, then the probability of an edge between $i$ and $j$ is just zero. If $j> i+ \Omega(\log n)$, then the expansion of the graph should be enough to argue that the existence of the edge $(i,j)$ happens with probability $n^{-\Omega(1)}$. This is because, for a fixed start vertex $v$, the distribution of the walk after a number of steps equal to the girth is uniform over a set of size $n^{\Omega(1)}$, and so has collision probability $n^{-\Omega(1)}$; every subsequent step should only decrease the collision probability (this is true for an actual random walk, but it should also be true for this non-backtracking walk), and so the collision probability, and hence the min-entropy, of the distribution stays $n^{-\Omega(1)}$, and the probability of hitting one of the $O(1)$ neighbors of $v$ is also $n^{-\Omega(1)}$.


Solving semidefinite programs in polynomial time We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (exponential) number of variables/constraints can also be solved in polynomial time, provided we can design a polynomial time separation oracle for them.

What about semidefinite programs (SDP)? What classes of SDPs can be solved exactly in polynomial time? When an SDP can't be solved exactly, can we always design an FPTAS/PTAS for solving it? What are the technical conditions under which this can be done? Can we solve an SDP with exponential number of variables/constraints in polynomial time, if we can design a polynomial time separation oracle for it?

Can we solve the SDPs that occur in combinatorial optimization problems (MAX-CUT, graph coloring) efficiently? If we can solve only within a $1+\epsilon$ factor, will it not have an effect on constant factor approximation algorithms (like 0.878 for Goemans-Williamson MAX-CUT algorithm)?

Any good reference on this will be highly appreciated.

The ellipsoid method and interior point methods can be extended to solve SDPs as well. You can refer to any standard-texts on SDPs for details. Here's one:
Semidefinite Programming. Vandenberge and Stephen Boyd, 1996.


What is an unambiguous language in the sense of Schützenberger? I'm reading Thomas Wilke's survey on the connections between Temporal Logic and finite automata, finite semigroups and first-order logic.

In Theorem 6 (by Kamp), the fragment $\mathrm{TL}[\mathsf{F},\mathsf{P}]$ (Temporal Logic with  modalities $\mathsf{F}$ (eventually) and $\mathsf{P}$ (eventually in the past)) is said to be equivalent to first-order logic with two variables.

After the statement of the theorem, Wilke mentions another connection from TL to formal languages:

  (...) the languages expressible in $\mathrm{TL}[\mathsf{F},\mathsf{P}]$ are exactly the unambiguous languages in the sense of Schützenberger [13]

where [13] cites Sur le produit de concatenation non ambigu. I can't pay for the paper and I can't find it anywhere else for download. What's more, I can't read French, even though I'd gladly try if I had the paper.

I've searched online for a while but I can't find a definition of "unambiguous in the sense of Schützenberger", and I guess it's not the same as in an "unambiguous context-free language", since $\mathrm{TL}[\mathsf{F},\mathsf{P}]$ is strictly less expressive than $\mathrm{TL}$, which is strictly less expressive than regular languages (unless it's the same definition, restricted to regular languages instead of context-free).

Does anybody have the definition, the paper, or know of a survey or book with this information?

An additional and related question: is there a (known) restriction to the syntax of regular expressions such that this class of unambiguous language is equivalent to the fragment of regular languages defined by those regular expressions? (as in the equivalence of star-free languages with first-order logic, for example).

Thanks in advance for your help!

Jean Berstel maintains a website with Schützenberger's collected papers. You can access the original paper (in French) here.
A definition of the unambiguous product you are referring to in English is given by Pin in Syntactic Semigroups, p.30:
"The product $L = L_0a_1L_1 \cdots a_nL_n$ is unambiguous if every word $u$ of
$L$ admits a unique factorization of the form $u_0a_1u_1 \cdots a_nu_n$ with $u_0 \in L_0, \cdots, u_n \in L_n$."
I recommend reading the following survey by Diekert, Gastin and Kufleitner for more background information. They refer to the concept of unambiguous product as "unambiguous monomial".

References:

J.-E. Pin, Syntactic semigroups, Chap. 10 in Handbook of language theory, Vol. I, G. Rozenberg and A. Salomaa (éd.), Springer Verlag, (1997), 679-746.
Volker Diekert, Paul Gastin, and Manfred Kufleitner. A survey on small fragments of first-order logic over finite words. International Journal of Foundations of Computer Science, 19(3):513-548, June 2008. Special issue DLT 2007.


An algorithm for calculating the probability of a disease spreading through a graph The following problem came up in my undergrad research project: You have some undirected graph. Some nodes are "sick" and some are not. The probability that a neighbour of a sick node becomes sick is (1 - q_i), where q is a number specific to the node under attack, ranging from 0 to 1. If a node succesfully resists an attack from a sick neighbor, it becomes immune and cannot get sick from any other node. What is the probability that any given node will become sick, given a graph A, some initial sick nodes, and a vector of q's characterizing the nodes?

I feel like this problem has been solved, but I'm having trouble finding sources. Any help or references to papers/books will be greatly appreciated.

Immunity seems to make your problem easier in one sense, as it means that infection can be modelled by a process that terminates after a linear number of infection attempts.  The stipulation that the probability of infection does not depend on the neighbours of a vertex also helps.  However, the model does not seem easy to analyse: the immune vertices in effect are removed from the graph, so a vertex may effectively become unreachable.
The infection, immune, and unreachable probabilities depend on the intermediate graphs created by the infection process.

It might be useful to start with cliques, paths, and cycles with a single initially infected vertex.  Cliques are trivial.  For a path with one infected endpoint the probability that the other endpoint becomes infected at some stage is the product of the probabilities of infection of all the intermediate vertices.  For a cycle, the probability depends on both paths; the longer path becomes relevant if an immune vertex appears on the shorter path.  Trees also have a single path between any two vertices, so can be handled as for the path case.

It might then be feasible to extend the analysis to $k$-connected graphs and regular grids, though this already seems quite tricky.

I am not familiar with literature that deals with this specific problem.  Here are some general comments and pointers.

Some relevant keywords are "contagion" (in the context of network models) and "percolation" (in statistical mechanics).  These models tend to focus on the behaviour of randomized processes that behave like the one you suggest.  However, different models focus on different parameters of interest, so you might have to examine several to find one that best matches the specific one you are interested in.

As an example, a lot of post-2008 work has applied contagion models to financial systems, since it has been argued that these models explain well the gridlock experienced at that time by the global financial system.

The Ising model is one of the simplest and earliest models that involve interacting parties in a graph, and has an extensive literature.

From a purely TCS perspective, computing the partition function of spin systems like the Ising model is equivalent to counting the solutions of a constraint satisfaction problem.  The mixing time is also often of interest.

Andrei Bulatov and Martin Grohe, The complexity of partition functions, TCS 348, 2005, 148–186.  doi:10.1016/j.tcs.2005.09.011 (preprint)
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, Matrix norms and rapid mixing for spin systems, Annals of Applied Probability, 19, 2009, 71–107.
doi:10.1214/08-AAP532


Succinct complete problems in DTIME(EXP(EXP(...))) I understand complete problems for $EXPTIME$ or $NEXPTIME$ formulated as succinct instances of e.g. $NP$-complete problems such as $3-SAT$. On input $x$, one efficiently computes a circuit $R(x)$ such that $R(x)$ is a succinct encoding of a satisfiable formula if and only if $x\in L$.

I am having trouble going beyond $(N)EXPTIME$. Take $DTIME(2^{2^{p(n)}})$. Are there analogue succinct problems here? This could take the form, on input $x$ one can compute a poly-size circuit $R(x)$ which on each input computes an exponential-size circuit which on each input returns a clause...

Aside from the fact that this is hard to grasp, what troubles me if whether one can guarantee that this hierarchy of circuits calling each other exists, i.e. that at every level the circuits of appropriate size exist. When we consider $NEXP$, we are directly verifying the tableau of a Turing-machine computation, so this is pretty straightforward. But a few levels up it becomes much less clear to me. (Ultimately I am interesting in moving up many levels of exponentiation, possibly even a polynomial number of exponentiations, which I believe would move me out of even $ELEMENTARY$?)

My question is, does anyone have pointers to literature discussing such problems? Or a good sense for what is the appropriate way to define "succinct" complete problems for classes that are so high in the time hierarchy?

See, e.g., Theorem 5 of

  Balcazar, Lozano, and Toran, The complexity of algorithmic problems on succinct instances (doi)

This theorem essentially lets you bootstrap up the tower of exponentials as desired, using the appropriate standard bounded version of the halting problem as being complete for most standard classes.


Infinite $\beta \eta$-reduction sequence implies infinite $\beta$-reduction sequence In Sorensen and Urzyczyn's book there is a lemma (1.3.11) which I am having a hard time proving.

1.3.11 Lemma:
If there is an infinite $\beta \eta$-reduction sequence starting with a term $M$ then there is an infinite $\beta$-reduction seqeunce from $M$.

Now the proof is sketched in the book but I am having trouble realising it:

Proof.
First observe that in an infinite $\beta\eta$-reduction sequence there must be infinitely many $\beta$-reduction steps (cf. Exercise 1.6). These $\beta$-reduction steps can be "permuted forward", yielding an infinite $\beta$-reduction. Indeed, by induction with respect to $M \to_{\eta} N$, one can show that $M \to_{\eta}N \to_{\beta}L$ implies $M \to_\beta P \twoheadrightarrow_{\beta \eta} L$, for some $P$.

So $\to_\eta$ is defined as the least compatible relation satisfying $\lambda x . f x \to_\eta f$. Where compatible means works with the syntax, i.e. $A \to B$ imples $M A \to M B$, $A M \to B M$ and $\lambda x . A \to \lambda x .B$.
The definition is similar for $\beta$ with the obvious reduction. The relation $\to_{\beta \eta}$ is the union of both. And $\twoheadrightarrow$ is the transitive-relfexive closure of said relation.
Exercise 1.6 was to prove that $\to_\eta$ is strongly normalising, which can be shown by considering a "depth" function on terms, and showing that this strictly decreases on $\eta$-reduction.
The problem I am having is I can't seem to understand how $\beta$ and $\eta$ interact.
Take for example $\lambda t. (\lambda  x . y) t$. Clearly we can $\beta$-reduce this to get $\lambda t . y$ or $\eta$-reduce it to get $\lambda x . y$ which are clearly equal but its not obvious to me in general.

How can this be proven? And better yet, are there any references for this? I can't seem to find much on $\eta$-reduction in lambda calculus.

As usual, the bible knows all, and Lemma 3.3.8 (p 66) gives the detailed proof of commutativity of $\beta$ and $\eta$ reductions.

Trying to reproduce it here would be tedious and wouldn't do it justice, so I'll include a picture:

You had the main idea right, it just takes a bit of practice to generalize from the specific examples.


Algorithm to find all intersections in set of simplices What is the fastest known algorithm to report all intersecting pairs amongst a collection of $n$ simplices, each with dimension at most $r \leq d$ embedded in $\mathbb{R}^d$ (for small $d$)?

In the case where $d=2$ and all simplices are line segments, this problem can be solved in $O((n+k) \log(n))$ time using the standard sweep line algorithm, where $k$ is the number of intersections.

Are there generalizations of this technique to higher dimensions and with higher dimensional simplices (for example, find all intersections of a set of triangles in 3D)?

For clarification, I am most interested in the case where the dimension, $d$, is small, so it would be reasonable to assume that the cost of testing intersection between two simplices is $O(1)$.  Under this assumption, there is a trivial $O(n^2)$ algorithm (just test all pairs), but it would be nice to be able to do better.

The motivation for this would be to generalize sweep line intersection to 3D or higher dimensions.  This would be useful for computing overlay operations (especially CSG) in 3D, or snap-rounding.  Conventional approaches to this problem rely on spatial partitioning trees, though the performance and analysis of these techniques is somewhat sketchy (ie purely empirical, and not always great in the worst case even in practice).  It would be nice to know a solution to this problem which is supported by rigorous analysis.

Yes. You can do better than the trivial $O(n^2)$ time bound, but you are not going to enjoy it....

You can reduce the problem of deciding if there are intersecting pairs of triangles to $O(n)$ ray shooting queries among triangles, and using some heavy machinery (i.e., range searching techniques) you would get something. See Theorem 7.1 in the paper below.

You should also get something as far as detecting all $k$ intersecting pairs, but the bound is going to be useful only if $k$ is truly small (say, between $n$ and $n^{5/4}$).

In practice, some quadtree based heuristic should work reasonably well, but I am just speculating.

https://www.cs.duke.edu/~pankaj/publications/papers/semi-range.pdf


Circle graph algorithm You are given N points on 2-D plane. How can I find out minimal radius of a circle which contains at least M of these points?

algorithm for code

I searched for smallest enclosing circle problem but that was not for at least m?

See

Sariel Har-Peled and Soham Mazumdar (2005), "Fast algorithms for computing the smallest $k$-enclosing circle", Algorithmica 41 (3): 147–157, doi:10.1007/s00453-004-1123-0.


Does P/poly $\neq$ NP/poly have any interesting implications? $P/poly = NP/poly$ implies $NP \subseteq P/poly$, which in turn has interesting consequences like the collapse of the polynomial hierarchy.

Are there interesting implications for $P/poly \neq NP/poly$?

Emil Jeřábek' comment answers the question:

  P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly

Note the corollary

  P/poly $\neq$ NP/poly implies P $\neq$ NP.

Proof of corollary:

P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly $\ $ (Emil's comment)
NP $\subseteq$ P/poly implies P/poly $=$ NP/poly $\ $ (implied by 1.)
P/poly $\neq$ NP/poly implies NP $\not\subseteq$ P/poly $\ $ (equivalent to 2.)
NP $\not\subseteq$ P/poly implies P $\neq$ NP $\ $ (P $\subseteq$ P/poly)
P/poly $\neq$ NP/poly implies P $\neq$ NP $\ $ (implied by 3. and 4.)

Proof of Emil's comment:
It is sufficient to show that NP $\subseteq$ P/poly implies P/poly $=$ NP/poly.

So let's assume NP $\subseteq$ P/poly.
Because SAT $\in$ NP there exists $p_{SAT}\geq k_{SAT}>0$ and a sequence of advice strings $s_n$ with $\left|s_n\right|\leq n^{k_{SAT}}$, a deterministic algorithm that can decide SAT instances of size $n$ in time $\leq n^{p_{SAT}}$, if it has access to $s_n$. WLOG, that algorithm can also decide SAT instances of size $\leq n$, because we can define a modified sequence $s'_n=s'_{n-1}s_n$ with $\left|s'_n\right|\leq n^{k_{SAT}+1}$, where all previous advice strings are included in $s'_n$.
Now let $L\in$ NP/poly be an arbitrary language, for which we need to show $L\in$ P/poly. There exists $p_L\geq k_L>0$ and a sequence of advice strings $l_n$ with $\left|l_n\right|\leq n^{k_L}$ and a nondeterministic algorithm that can decide $L$ instances of size $n$ in time $\leq n^{p_L}$, if it has access to $l_n$.
For each $w$ with $|w|=n$, a SAT instance of size $\leq c\cdot n^{p_L}$ can be computed (in time $O(n^{p_L})$) that is satisfiable exactly if $w\in L$.
So for the sequence of advice strings $t_n=l_ns_{c\cdot n^{p_L}}$ with $|t_n|\leq n^{k_L}+(c\cdot n^{p_L})^{k_{SAT}}$, the combination of the deterministic algorithms from 2. and 4. gives a deterministic algorithm that can decide $L$ instances of size $n$ in time $O((c\cdot n^{p_L})^{p_{SAT}})$, if it has access to $t_n$.
Because $L\in$ NP/poly was an arbitrary language, this shows NP/poly $\subseteq$ P/poly, under the assumption that NP $\subseteq$ P/poly.

All the above proofs relativize, because the existence of NP-complete problems is also true in relativized worlds. This suggests that it is fruitless to search for a proof that P/poly $\neq$ NP/poly. However let's summarize the removed motivation section from the question as "The advice string could be a formal axiomatic system (automatically guaranteed to be consistent, evil grin) whose strength is quickly increasing with input length, and NP is extermely good at exploiting this advice." If one is not very careful that "existence of a sequence of advice stings" only has "formal" meaning relative to a fixed formal system, that setup is likely to allow the construction of apparent paradoxes. But the construction of such paradoxes might be fun nevertheless, and perhaps they might even suggests ways how to construct independence proofs (for sufficiently weak formal systems).


Separation of classes with different amounts of advice? The time hierarchy theorem lets one show that, for example, there are problems in P that cannot be solved in time less than const*n^2 by a Turing machine.  But give the Turing machine some advice and all bets are off.  One can't yet show that even a linear size circuit can't solve all of PSPACE.  So, what if we try to compare two different classes in which both have advice?  For example, can one separate polynomial space with logarithmic advice from linear time with linear advice?  That's just a made-up example question, I am wondering what general results there are along these lines.

Let $s(n) \ge n$ be some function. It can be proven that:

$\mathbf{DSIZE}(s) \subseteq \mathbf{DTIME}(s^2) / F(O(s\log s))$

Here, $\mathbf{DSIZE}(s)$ denotes the set of languages decidable by deterministic circuits of size $s$. The notation $\mathbf{K/F}$ denotes the complexity class $\mathbf{K}$ with advice function from the set $\mathbf{F}$, defined as:

$F(f) = \left\{h \colon \{0,1\}^* \to \{0,1\}^* \mid |h(x)| \le f(|x|) \text{ for all } x\right\}$.

In addition, let $d(n) \ge \log n$ be another function. Then:

$\mathbf{DDEPTH}(d) \subseteq \mathbf{DSPACE}(d) / F(2^{O(d)})$

where $\mathbf{DDEPTH}(d)$ denotes the set of languages decidable by deterministic circuits of depth $d$.

Edit: two more inclusions:

For $t(n) \ge n$ we have $\mathbf{DTIME}(t) \subseteq \mathbf{DSIZE}(t \log t)$,
and for $l(n) \ge \log n$ we have $\mathbf{NSPACE}(l) \subseteq \mathbf{DDEPTH}(l^2)$.

  For proofs, see section 2-3 of Heribert Vollmer's book.

Using these inclusions, and time/space hierarchies, one can build hierarchies for non-uniform complexity classes.

Edit 2:

You may combine the above results with the following results on hierarchies for classes with advice:

Time Hierarchies for Computations with a Bit of Advice.
Unconditional Lower Bounds Against Advice.


Is there a survey of the semantics of various programming language features? Is there a survey (from paper, book chapter, tutorial, links, ...) of the semantics of various programming language features? I was originally overwhelmed by the features of D in here http://www.digitalmars.com/d/2.0/comparison.html

I would like to see what I could possibly get from here, although I have asked a similar question on stackoverflow and understand these two sites have different perspectives.

Really appreciate your reply! Thanks to Dave Clarke for his suggestion on meta！

I don't know of any survey of the semantics of various language features, though
there are many books dealing with the semantics of programming languages. Here are a few of the more comprehensive ones, which also deal with less standard constructs:

Design Concepts in Programming Languages by Franklyn Turbak, David Gifford and Mark Sheldon. A mammoth book full of semantics of many different language constructs.
Concepts, Techniques, and Models of Computer Programming by Peter Van Roy and Seif Haridi. This book focusses mainly on the concepts in terms of the language Oz. Every example in the book runs. At the end of the book there is a chapter or two discussing the formal semantics of the language constructs.

More classical texts which put more emphasis on the semantic techniques, rather than on the variety of programming language constructs, include:

Types and Programming Languages by Benjamin Pierce. The book on type systems. Mainly focusses on functional language constructs, while increasing the sophistication of the type system. It also covers Featherweight Java, a core calculus of Java.
Transitions and Trees by Hans Huttel. A nice introduction to operational semantics, covering a variety of languages constructs of increasing complexity.
Semantics with Applications by Hanne Riis Nielson and Flemming Nielson. An introduction to various semantics styles, including some non-obvious applications of them. A great read!
The Structure of Typed Programming Languages  by David A Schmidt. A solid foundational book.
Semantics of Programming Languages: Structures and Techniques by Carl A Gunter. Another  solid foundational book.

Finally, a work-in-progress, generously available for download, Practical Foundations for Programming Languages by Bob Harper  covers a lot of different programming language features, ensuring that everything is formalised along the way.

I should add that if you ask a more specific question, you'll get a more specific answer.  Many scientific papers are out there giving semantics to various programming language features. If you were interested in a specific feature, then I could dig up a paper or two on that feature.


Persistent data structures in RAM computational model Always when I read about any efficient persistent data structures they use pointer computational model. I'm wondering if you know any efficient implementation which uses power of RAM model?

Paul F. Dietz's "Fully Persistent Arrays" uses a variant on van Emde Boas trees, which rely on arrays and also on integers being represented as words.
Brodal et al.'s "Fully Persistent B-Trees" relies on arrays.
Davoodi et al.'s "Cache-Oblivious Persistence" applies a persistence transform to data structures that don't necessarily work in the pointer model.
The Bentley-Saxe logarithmic method, also known as cache-oblivious lookahead arrays is naturally partially persistent, and relies on arrays for the insert time to be $o(\log_B n)$ in an external-memory setting.


Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?

New answer:
The number of pseudo line arrangements is 2^{Theta(n^2)} http://page.math.tu-berlin.de/~felsner/Paper/numarr.pdf . Which is in turn can be used to bound the number order type of n points in the plane. Thus if you want to check some concrete conjecture on point configurations in the plane, you are going to get your desired running time. Examples of algorithms using this approach and use this approach are here: http://www.ist.tugraz.at/aichholzer/research/rp/triangulations/ordertypes/ . If you do not aggressively cut the search space for the specific conjecture you are checking, you would get the running you want.

In a similar direction, checking if a generic property holds for all binary n*n matrices, would take this running time. This in particular, the time it would take to verify a "generic" property over graphs over n vertices. As a "silly" example, think about a Ramsey type conjecture: Every graph over n vertices contains either a clique or an independent set of size $\Theta(\log n)$. Ha! This running time is explicitly mentioned in the Wikipedia page: http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers.

Old answer:
Some variants of Cylindrical algebraic decomposition if my memory serves me right.

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


What was the significance of Leslie Valiant's, "A Theory of the Learnable?" It seems like two of the main takeaways were that there is a natural limit to what computers can learn, and learning is bounded by polynomial algorithms. Why was his paper significant in the broader area of machine learning?

I think that "there is a natural limit to what computers can learn", while definitely true, is not one of the main takeaways of Valiant's paper, for two reasons. One is that I could not find any discussion of lower bounds or no-free-lunch results in this paper. Two is that surely statisticians had been aware of such fundamental limitations on learnability prior to Valiant, if only as folklore.

I'd say the reason that paper has had such an impact is that it formalized an intuitively appealing learning model (what came to be known as PAC), which turned out to have a rich and satisfying mathematical structure, as well as numerous generalizations and extensions. Of course, finite-sample bounds had been obtained by Vapnik and Chervonenkis previously, but Valiant placed learning in an algorithmic setting by (among other things) emphasizing the importance of representation. In particular, he argued that DNFs are a natural human-interpretable representation and wondered whether these can be efficiently PAC-learned. (We now know that properly PAC-learning 3-term DNFs in polytime would imply NP=RP, but the agnostic case is still an active area of research and a major open question, as far as I know).

In summary: by Valiant's own admission, the statistical contributions of the paper are minor. He doesn't even need the full power of VC theory, since he mostly (exclusively) deals with discrete function classes, for which cardinality bounds + Chernoff do just fine. The reason that this paper has had such an impact on CS -- and indeed, probably the main reason why machine learning, by default, resides in CS departments -- has mainly to do with the computational aspects.


1st & 2nd quantization from TCS Last year I attended Scott Aaronson's talk Hawking Quantum Wares at the Classical Complexity Bazaar. Being intrigued by his argument that "[e]ven if quantum mechanics hadn't existed, theoretical computer scientists would eventually have had to invent it", I have been thinking about how we can derive the first and second quantization in quantum mechanics from theoretical computer science.

First quantization is basically the quantization of properties of a unit quantum system and second quantization is the quantization of the electromagnetic field. Is there some way that theoretical computer science could entail these two ideas? I can recognize some "quantumnesses" in theoretical computer science, including

enumeration of set elements,
enumeration of interactions with oracles, and
discrete states of Turing machine,

but I am having a hard time relating them to first and second quantization.

I would amend your definition of second quantization.  It is not a procedure that is applied only to the electromagnetic field.  It is more properly a process in which something like the Schrodinger equation is re-interpreted as a classical field, which is then quantized.  This is the standard old-fashioned way to move from single-particle quantum systems to multi-particle quantum systems in which particle creation and annihilation can be described via unitary operators.

I'm not sure that the paradigm of second-quantization makes sense in the context of quantum computation.  To do so, one would need to interpret the "first-quantized" theory as a system which conserves something like particle number.  The "second-quantized" theory allows for a description of systems with different particle numbers.  Qubits obey neither Bose-Einstein nor Fermi-Dirac statistics and thus there is nothing analogous to "particle-number" in a qubit system.  From this point of view it is hard to see that "second-quantizing" a qubit system would lead to something sensible.


White-box sparse interpolation Let $C$ be an arithmetic circuit that represents a polynomial $f\in\mathbb K[x_1,\dotsc,x_n]$, with the promise that $f$ has at most $k$ nonzero terms. What is (known about) the complexity of computing $f$ in its sparse representation, given $C$?

I am interested in deterministic and randomized complexity, and in the link with PIT. In particular, does the promise that $f$ is sparse imply good algorithms? A priori, I am more interested in the case of $\mathbb K$ being some finite field, though results over other fields may be relevant.

There are deterministic and randomized algorithm running in time $\mathrm{poly}(n,d,k)$, where $n$ is the number of variables, $d$ is the degree and $k$ is the sparsity. AFAIK, the results are stated for characteristic zero fields but work over any field large enough (again, polynomially large in the parameters).

This paper of Kaltofen and Yagati discusses both the randomized algorithm of Zippel and the deterministic algorithm of Ben-Or and Tiwari, and then goes on to present some improvements.


Data structures for embedded simplicial complexes I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar graphs, and generalized maps which further generalize combinatorial maps to allow for non-orientability.

From Wikipedia, a combinatorial map is defined as an $(n+1)$-tuple $(D, \beta_1,\dots,\beta_n)$ such that:

1) $D$ is a finite set of darts,

2) $\beta_1$ is a permutation on $D$,

3) $\beta_2, \dots, \beta_n$ are involutions on $D$,

4) $\beta_i \circ \beta_j$ is an involution if $i + 2 \leq j$.

Here's my understanding of the definition. The set $D$ should contain $n+1$ darts for each $n$-simplex as this is the natural generalization of a half-edge in a planar rotation system. The permutation $\beta_1$ describes the cyclic order in which the $n$-simplices are incident to a common $(n-1)$-simplex. The involutions $\beta_2,\dots,\beta_n$ allow you to move from one $(n-1)$-simplex to another along a common $n$-simplex, which generalizes the one involution needed to define the half-edges in a planar rotation system.

I don't understand what condition 4 is used for, however Wikipedia states that it is included to "fix constraints which guarantee the topological validity of the represented object: a combinatorial map represents a quasi-manifold subdivision."

Here are my questions about this data structure:

1) Are my interpretations of conditions 1-3 correct?

2) What is the geometric interpretation of condition 4?

3) Can a combinatorial map be used to encode any orientable embedded simplicial complex, or just quasi-manifold subdivisions?

4) What is a quasi-manifold subdivision?

5) Why does the definition of a combinatorial map fail for non-orientable complexes?

First you can read the CGAL documentation that can help you to understand combinatorial and generalized maps, since it provide several examples. You can also read the book "Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing".

Now some answers:

1) I don't think. In a combinatorial map, in 2D, a triangle is described by 3 darts. In 3D, a tetrahedron is described by 4 triangles, thus 12 darts. Etc...

Given a dart $d$, each permutation, except $\beta_n$, stay in the same n-simplex. A dart corresponds to a n+1-tuple (vertex, edge, face, ..., n-simplex), and each $\beta_i$ (except $\beta_1$) can be seen as a switch for the $i^{th}$ element of the tuple (each switch also switches vertices).

2) Condition 4 ensures that when two n-simplices are glued along one of their (n-1)-face, all the darts of the two (n-1)-faces are correctly identified two by two (cf. the following example).

3) Only quasi-manifold. For example in 3D, you cannot represent two tetrahedra that share only a common vertex, since this is not a quasi-manifold.

4)  A dD quasi-manifold is an object obtained by taking some isolated d-cells, and allowing to glue d-cells along (d-1)-cells (cf. this section).

5) Let us consider one simple example in 2D. Take a square with four edges a,b,c,d. Now you can identify edges a and c to form either an orientable strip or a Mobius strip. Thus you need two different type of identification. This is not possible with combinatorial maps but this is possible with generalized maps since one edge in 2D is described by two darts, allowing to choose which pair of darts are identified (cf. the example here).

Hope this helps, and welcome into the fabulous world of combinatorial maps !


Computational complexity of classifying with an already-trained SVM If I have a support vector machine which has already been trained, what is the computational complexity of classifying a new example using that machine?  I care about both time and space complexity.

Does the answer change if the underlying metric space is unusual -- for instance, Damerau-Levenshtein edit distance (computing which is $O(n^2)$ time and space for strings of equal length) instead of Euclidean ($O(n)$ time and $O(1)$ space)?

(This is related to Computational complexity of learning (classification) algorithms - fitting the parameters but that's about the training process.)

(Edit: the paper that sparked this question is http://www.cs.stonybrook.edu/~xcai/fp.pdf )

If you're classifying using SVMs, then the underlying metric space is always a Hilbert space. If your classifier is linear, then the running time of the classification is linear in the dimensionality of the data (or the number of features).

If the classifier (in general) involves some kernel, then the classifier is expressed in terms of the number of support vectors, and the classification is linear in the number of such vectors. Processing each vector takes time proportional to the kernel computation time (which could be constant, or linear in the data dimension, or something else)