Face-walks in rotation systems for graphs Given a graph $G$, a rotation system for $G$ is composed of two elements:

$\pi = \{\pi_v: v\in V(G)\}$, where $\pi_v$ is a cyclic permutation of the edges incident on $v$. Thus if $e$ is an edge incident on $v$, $\pi_v(e)$ is another edge incident on $v$, and we say that $\pi_v(e)$ comes after $e$ at $v$.
$\lambda:E(G)\rightarrow \{-1,1\}$ is a function that assigns to each edge a sign $\pm 1$.

Given a rotation system for a graph $G$, we define a face-walk as a walk in $G$:

$$v_0e_1v_1e_2v_2...e_nv_0$$

such that:

$e_{i+1}=\pi_{v_i}^{r_i}(e_i)$ for $1\leq i<n$;
$e_1=\pi_{v_0}(e_n)$;
$\lambda(e_1)\lambda(e_2)...\lambda(e_n)=1$.

Here, $r_i=\lambda(e_1)\lambda(e_2)...\lambda(e_i)$ and $\pi_v^{-1}$ denotes the inverse cyclic permutation to $\pi_v$ (that is, $\pi_v^{-1}(e)$ gives the edge that comes before $e$ at $v$).

According to Theorem 3.2.2 in Topological Graph Theory by Gross and Tucker:

  Every rotation system on a graph $G$ defines (up to equivalence of imbeddings) a unique locally oriented graph imbedding $G\rightarrow S$. Conversely, every locally oriented graph imbedding $G\rightarrow S$ defines a rotation system for $G$.

In the same book, an algorithm is given to trace the faces of the embedding. One starts with any vertex $v_0$ and any edge $e_1$ incident on $v_0$ and proceeds to complete a face-walk. They claim that this will give a face boundary of the embedding. To understand this, I need to see a proof for the following two statements:

Given any vertex $v_0$ and any edge $e_1$ incident on $v_0$, one can complete a face-walk starting at $v_0e_1$. Clearly a sequence $v_0e_1v_1e_2v_2...$ can be extended indefinetely. The question is whether this sequence will be periodic.
Each edge either belongs to exactly two distinct face-walks (and appears once in each), or it appears exactly twice in one face-walk.

Neither of these claims is proved in the book.

If the sequence $v_0e_1v_1...$ is extended indefinetely without going back to $v_0e_1$, then since the graph is finite, some couple vertex-edge is repeated and hence it is periodic (since the facewalk always continues the same way after meeting this couple vertex-edge), so it looks like $v_0e_1v_1e_2.. v_{i-1}e_{i}v_ie_{i+1}...v_{i+j}e_{i+j+1}v_ie_{i+1}...v_i...v_i$ and so on indefinitely. We can assume that $e_i\neq e_{i+j+1}$ otherwise the loop never starts.
But then we have $e_{i+1}=\pi_{v_i}(e_i)$ and $e_{i+1}=\pi_{v_i}(e_{i+j+1})$, so $e_i=e_{i+j+1}$, yielding a contradiction. (I intentionnaly left out the $\lambda$ for the sake of clarity, but it works the same for non-pure rotation systems by replacing couple (vertex-edge) by triple (vertex-edge-value of $r_i$ when arriving at the vertex)).
For an edge $e$ attached to vertices $v_1$ and $v_2$, $e$ appears in the facewalks starting by $v_1 e$ and $v_2 e$ (possibly the same facewalk !). Moreover, it only appears in facewalks including $v_1 e$ and $v_2 e$ (where would it come from otherwise ?), so that makes exactly two facewalks (or twice the same). Edit : To be more precise, a facewalk is uniquely defined by a triple (vertex-edge-value of $r_i$ when arriving at that edge). But arriving at $v_1 e$ with orientation (value of $r_i$) -1 yields the same facewalk (up to reversing it) as arriving at $v_2 e$ with orientation +1, so there really are only two different facewalks passing through $e$.


Are there alternatives to using polynomials in defining the different notions of efficient computation? Is invoking polynomials in defining the different notions of efficient computation the real obstacle to resolve the P vs NP problem? Do we need a paradigm shift by redefining what constitute an efficient computation?

From the very beginning $P$ has drawn flak for allowing high degree polynomials to count as efficient (Edmonds essentially introduced $P$ to argue that his $O(n^4)$ matching algorithm should be considered efficient, but for computers in 1965 $O(n^4)$ was definitely not efficient), but there are very good reasons that the definition has stuck:

Polynomials have nice closure properties.  If $O(n)$ is efficient, and we allow an efficient algorithm to call an efficient subroutine a reasonable number of times, we are forced to conclude that $O(n^2)$ is efficient too, and iterating this reasoning leads us to conclude that $O(n^c)$ is efficient for all $c$ if we want to avoid a totally arbitrary cutoff.
$P$ is robust to changes in the underlying model of computation.  Complexity theory is about what problems are solvable in some reasonable model of computation.  There are a huge variety of equivalent models of computation that can simulate one another in polynomial time (Turing machines, register machines, stack machines, and other stranger models) and tons of variations (how many tapes does your Turing machine have?  How many states?), and we have no real reason to favor one over another.  If we design an algorithm for a RAM but need to preserve our definition of efficient from model to model, then we need to allow polynomial overhead for simulation.  Aliens may well have computer totally different from anything we have imagined, but their definition of $P$ would be the same.
$P$ is robust to technological advancement.  History has shown that computer science research that is not future-proof will quickly lose its relevance.  Over time, as computing power has increased, the definition of "truly efficient" has expanded to include larger polynomials, but $P$ has remained relevant.
In practice, problems requiring high degree polynomials are actually rarely an issue.  Generally, the difficult step is getting from exponential time to some polynomial, and once we have an algorithm in $P$ it is relatively easy to reduce the degree to something small.  There is an old joke that I have heard in several talks: "every time someone proves a problem is in $P$ Bob Tarjan makes it linear."


Stephen Hawking's impact on computer science In light of Stephen Hawking passing away today, I was wondering whether any of his results have direct impact on cs?

The obvious candidate would be in quantum computing, or rather the construction of a physical quantum computer, but perhaps there are results that have other impact.

I am familiar with his work only on the popular-science level, so this is not really a research-level question, but perhaps it has research-level answers.

EDIT: following the answer, I don't mean his recent concerns about AI. That is not really a contribution to CS, more of a philosophical/sociological point. I aim more for mathematical results, or connections of physics to computing.

He didn't have any major impact on computer science.

His writing in computer science are limited to popsci and more recently raising public concerns about AI.


Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks? The only examples of $\sharp P_1$ complete problems I've seen are fairly abstract : e.g. here https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf

Valiant proves that there exists a $\sharp P_1$ complete sub-pattern matching type-problem, but he doesn't give it explicitly.

I know it was conjectured ( for example, it's mentioned here: https://www.sciencedirect.com/science/article/pii/S030439750300080X ) that the number of self avoiding walks of length $n$ might be a $\sharp P_1$ complete problem. Has there been any progress on this problem? Or are there similar counting problems (some explicit combinatorial family) which have been shown to be $\sharp P_1$ complete?

As someone with a long time interest in this complexity class, I don't believe there has been any significant work on $\#P_1$ since. (I was a Ph.D. student of Mitsu Ogihara, the second author of the paper you cite, and actually raised - in informal discussions with Mitsu - the open question you cite; of course, all the actual results on this problem are due to Mitsu and his coauthors only, I did not contribute to any of them)

What is known is that $\#P_1$ is a rather weak class: whereas (by Toda's theorem) $\#P$ is hard for the polynomial hierarchy, the assumption $\#P_1 = FP$ has substantially weaker implications (P=BPP). This is another result due to Mitsu.

There are interesting complexity questions in enumerative combinatorics. But (naturally as it may be) no connection  seems to have been made yet to the class $\#P_1$.


An explicit separation between time-constructibility and space-constructibility? Show a function $f(n)$ which is space-constructible but not time-constuctible.

Is this problem related to a possible separation between complexity classes DTIME(f(n)) and SPACE(f(n))?

A function $T \colon \mathbb{N} \to \mathbb{N}$ is time constructible if there is a Turing machine $M$ which, on input $1^n$, computes the function $x \mapsto T(|x|)$ in time $O(T(n))$.

A function $S \colon \mathbb{N} \to \mathbb{N}$ is space constructible if there is a Turing machine $M$ which, on input $1^n$, computes the function $x \mapsto S(|x|)$ in space $O(S(n))$.

Some texts require that time/space constructible functions be non-decreasing. Some texts require the time constructible functions satisfy $T(n)\ge n$, and the space constructible functions satisfy $S(n)\ge \log n$. Some texts do not make use of the $O(\cdot)$ notation in the definition.

Anyway, it is easy to show that every "ordinary" function $f$, satisfying $f(n)\ge \log n$ and $f(n) = o(n)$ is space constructible, but not time constructible.

The constructibility problem is not directly related to possible separation between complexity classes DTIME(f(n)) and SPACE(f(n)). However, the statement of time and space hierarchy theorems incorporates the constructibility. For example:

Time Hierarchy Theorem
If $f$, $g$ are time-constructible functions satisfying $f(n)\log f(n) = o(g(n))$, then
$\mathbf{DTIME}(f(n))$ is a proper subset of $\mathbf{DTIME}(g(n))$.

See Arora & Barak's book or Papadimitriou's for more information. (The latter uses the term "proper complexity function" to refer to one that is both time and space constructible.)


For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this? I want to be very specific. Does anyone know of a disproof or a proof of the following proposition:

$\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N},$

$\forall G, H \in STRUC[\Sigma_{graph}] (min(|G|, |H|) = n, G \not\simeq H),$

$\exists \varphi \in \mathcal{L}(\Sigma_{graph}),$

$|\varphi| \leq p(n) \wedge qd(\varphi) \leq Clog(n)^k \wedge G \vDash \varphi \wedge H \nvDash \varphi.$

Intuitively, this should be true if all non-isomorphic graphs can be distinguished using "$Clog(n)^k$ local" statements, and I'd imagine that this is false. Of course any graph can be distinguished using polynomial quantifier depth, as you can simply specify your graph modulo isomorphism:

$\varphi = \exists x_1 \exists x_2 \exists x_3 ... \exists x_n (\forall x (\bigvee_{i \in V_G} x = x_i) \wedge (\bigwedge_{(i, j) \in E_G} E(x_i, x_j))) \wedge (\bigwedge_{(i, j) \notin E_G} \neg E(x_i, x_j))) \wedge (\bigwedge_{(i, j) \in V_G^2 \mid i \neq j}x_i \neq x_j).$

Edit: So it seems that the locality intuition I had is false. A formula of quantifier depth $k$ has Gaifman locality bounded by $O(3^k)$, which means that a log depth formula is basically global. For this reason, I have a hunch the proposition will turn out to be true, which would be much harder to prove in my opinion.

Thanks to my colleague Maxim Zhukovskii for suggesting this answer.

It turns out that the answer is negative, and the counterexample is rather simple. Just take $G=K_m\sqcup \overline{K_m}$ and $H=K_{m+1}\sqcup \overline{K_{m-1}}$ for $n=2m$ and $G=K_m\sqcup \overline{K_{m+1}}$ and $H=K_{m+1}\sqcup \overline{K_m}$ for $n=2m+1$. (Here $K_s$ is an $s$-clique and $\overline{K_s}$ is a set of $s$ isolated vertices). By considering the Ehrenfeucht game one can show that in the first case the minimal possible depth is $m$ and in the second case it is $m+1$.

It was shown in the paper "The first order definability of graphs: Upper bounds for quantifier depth" by Oleg Pikhurko, Helmut Veith and Oleg Verbitsky that this bound is almost tight and any two $n$-vertex graphs are distinguishable by a formula of depth $\frac{n+3}{2}$.


Computation of max H-free sets In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question, and a hard one at that.  Let's consider the more general question of finding (the size of) a largest H-free set in a graph, where H-free means that it does not induce a subgraph that contains a copy of the fixed graph H as an induced subgraph.

For fixed graph H, given input graph G, is it NP-hard to determine the size of a largest H-free set in G?

Is there a sensible way to construct a "table" of graphs H (or classes of H), so as to fill in the entries with correct yes or "no" answers to the above question?  (Let's pretend that "no" = P, and even that a "no" entry means there is a polytime algorithm to generate a largest H-free set.)

Failing that, are there non-trivial classes of H for which the answer is yes? ... no?

I was digging around, looking into two queries about generalised/H-free chromatic numbers --- here and here --- when it occurred to me that the (ostensibly simpler) "dual" problem of an H-free analogue of independence number might also be open.  I am aware of classical papers on a related problem for random graphs, cf. e.g. Erdos, Suen and Winkler (1995) or Bollobas and Thomason (2000), which are in a still very active line of research.  So perhaps there is already some work that I have not seen yet addressing this more basic question and that a rough internet search did not uncover (hence the reference-request tag).

Suppose $H$ has at least two vertices. The family of all $H$-free graphs is hereditary on induced subgraphs and the property of being $H$-free is non-trivial, where a property is non-trivial if it is true for infinitely many graphs and it is false for infinitely many graphs. Thus, the result of Lewis and Yannakakis [1] applies, showing that for all $H$ with at least two vertices, the problem is NP-complete.

[1] John M. Lewis, Mihalis Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. J. Comput. Syst. Sci. 20(2): 219-230 (1980)


New theories and publications on computer science When someone develops a new theory on computer science, specifically in artificial intelligence domain, which is barely on schetch (so there are no measurements, nor simulations, nor finished code or ready application) with just a mathematical and conceptual description, in which scientific journals people use to publish these theories/concepts?

I can think of two cases where this (more or less) happened.

Valiant published his first paper on PAC learning in Communications of the ACM 27 (1984). Charlie Bennett got Stephen Wiesner's paper on quantum cryptography published in SIGACT News 15 (1983). I believe that at the time of publication, the editors had more latitude in accepting articles without extensive peer review than in the standard model of refereed journals.

In both cases, the idea turned out to be enormously valuable, and I am sure the prestige of Valiant and of Bennett helped the work get published. In both cases, the research was quite a bit better worked out than "barely a sketch", but it was still very sketchy, and not completely convincing to contemporary researchers.

If you are an unknown researcher, in order to get anybody to pay attention, you probably need to work out your ideas at least as well as they were worked out in these two cases, and even then I am not sure whether you could get sketchy ideas published without having the backing of a respected researcher (as Wiesner did).v

Ralph Merkle did not succeed in getting his sketchy ideas on what was to become public-key cryptography published until after Diffie, Hellman, Rivest, Shamir and Adelman had worked out the sketchy ideas in enough detail to convince everybody they were worthwhile. Fortunately, somebody put him in touch with Diffie and Hellman, who were clever enough to see the value of his ideas, talented enough to work them out in some detail, and honest enough to give him his fair share of the credit. See this article.


Maximum matching versus preferential assignment There are several ways to solve the marriage problem. The "preferential assignment" approach consists in forming couples on the basis of preferred characteristics expressed by each individual. An alternative approach consists in selecting preferred partners among lovers: suppose that you have the graph $G$ of sexual relations, and that each relation $e$ is rated with some preference factor $w(e)$, then computing a maximum weighted matching in $G$ would aim at optimizing the sexual adequacy between lovers.

If there are only heterosexual relationships with two sexes (men and women), then this is a bipartite matching problem, which is conjectured to be in $NC_2$ . Now suppose that a devious adversary had the following abilities: (i) control of the sexual performances of the individuals, (ii) ability to solve parallel problems efficiently. Then this adversary could trick the heterosexual group into forming "bad unions" in a pessimistic sense, i.e. leading to increased instability or corruption.

So my question is: what are the remedies to this problem? Does the introduction of same-sex relations or ternary relations change the situation? I suspect that the goal would be to obtain a P-complete matching problem to defeat the parallel adversary.

After some introspection, I'd like to suggest the following natural problem. A  skew-symmetric digraph is a digraph $G$ where each vertex comes in two copies $v,v'$ (possibly identical) and such that for each arc $(u,v) \in A(G)$ we also have $(v',u') \in A(G)$. The problem consists of packing cycles in a skew-symmetric digraph under a weight constraint. That is to say, we are given a ssd $G = (V,A)$, a weighting $w : V \rightarrow \mathbb{N}$ s.t. $w(v') = w(v)$ for each $v \in V$, and an integer $k$, and we seek a family of $k$ cycles $\cal{C}$ in $D$ such that (i) $V(\cal{C})$ has maximum cardinality, (ii) each $C \in \cal{C}$ is skew-symmetric, i.e. if it contains $(u,v)$ then it also contains $(v',u')$, (iii) each vertex $v$ is contained in at most $w(v)$ cycles of $D$.

This problem would generalize two well-known problems in combinatorial optimizations: (1) maximum matchings in undirected graphs and (2) maximum $k$-chains in posets. Here is a sketch of the reductions. For problem (1) we start with an undirected graph $G$, and we let $D$ be the symmetric digraph obtained from $G$ with each vertex self-symmetric, assigning a weight one to each vertex. For problem (2) we start with a poset $P_0$ with underlying digraph $D_0$, and we let $D$ be the digraph obtained by taking the disjoint union of $D_0$, its symmetric copy, and arcs $(v,v'), (v',v)$ for each vertex $v$ of $P$; we assign a weight one to each vertex.

I'm not sure about the practical application of your problem, but I expect it to be P-hard: a reduction from 3HornSat to the weighted version seems possible although I didn't check the details. If this problem turned out to be in P (with a corresponding min/max result) it would be very interesting, at least from a theoretical standpoint.


Min weight perfect matching with even number of red edges Consider a weighted graph with some red edges.
We are interested in finding a perfect matching, such that the number of red edges is even, and under the previous constraints, the weight is minimized.

Is this problem solvable in polynomial time? Even for bipartite graphs?

What about a natural extension. The case where there is a constant number of colors, and the number of edges of each color in the matching must be even.

I think your problem is solvable in randomized polynomial time, if the weights are bounded polynomially in the size of the graph. You can use an approach based on the algebraic matching algorithm by Mulmuley, Vazirani, and Vazirani. It has been useful for similar applications in the past, see for example Proposition 9 and the preceding discussion in Daniel Marx's paper https://doi.org/10.1016/j.ipl.2003.09.016 .

In randomized polynomial time, you can determine whether there is a perfect matching whose weight is exactly a prescribed value, in an integer-weighted graph with weights bounded polynomially in the graph size. Now, say your graph has $n$ vertices and the maximum weight is $W$. Re-weight the red edges of the graph as follows: if the original weight was x, the new weight becomes $(nW+1) + x$. (I also assume all weights are nonnegative, which can easily be done by adding the same constant value to all of them.) Then observe the following: any perfect matching in the re-weighted graph whose total weight is in the interval $[0 ... nW]$, is a perfect matching with 0 red edges. If its total weight is in the interval $[2(nW+1) ... 2(nW+1) + nW]$, then it is a perfect matching with exactly 2 red edges. In general, from the weight range you can infer the number of red edges.

Hence to find a minimum-weight matching with an even number of red edges, it suffices to go over all the weight ranges corresponding to matchings with an even number of red edges, testing for each weight in that range whether there is a perfect matching of that weight, and scaling the weight of each re-weighted matching back based on the number of red edges contained in it, to figure out which of these corresponds to the minimum-weight even-red perfect matching in your original graph. By standard self-reduction techniques, you can then also extract the matching itself rather than just the value, but you might have to boost the success probability by doing multiple trials to get an overall good success probability when doing self-reduction.


Solving a system of sums-of-powers polynomials What is the complexity of calculating the values of the integers $x_i$, where $0 \leq x_1 < x_2 < \dots < x_k < n$, given only the values $s_m = \sum_{i=1}^k x_i^m$? for $1 \leq m \leq k$?

If this can be solved in $f(n,k)$ space, it can be used to solve the following problem:

Given $S \subset \mathbb{Z}_n$ where $|S| = n-k$, determine $\mathbb{Z}_n \backslash S$ in $\tilde O(f(n,k))$ space.

This is done by calculating $\sum_{s \in S} s^i$ for $1 \leq i \leq k$ and $\sum_{s \in \mathbb{Z}_n} s^i$ for $1 \leq i \leq k$.

I think your question is closely related to the set reconciliation problem, which is solved in this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.5338

The problem of set reconciliation is to given two sets $A, B \subseteq [n]$ find $A \backslash B$ and $B \backslash A$ with as less communication as possible. If $B = [n]$, then you just need to find $\bar A$. Authors provide an algorithm with $O(k \log n)$ communication complexity.

Basic idea of the algorithm is to find small prime number $p$ greater than $4n$ and compute next two polynomials $\chi_A(x) = \prod_{a\in A} (x - a)$ and $\chi_B(x) = \prod_{b \in B} (x - b)$ in $\mathbb{F}_p$ on $2 \cdot k$ different points.

It can be easily shown that $$\frac{\chi_A}{\chi_B} = \frac{\chi_{A \cap B} \cdot \chi_{A \backslash B}}{\chi_{A \cap B} \cdot \chi_{B \backslash A}} = \frac{ \chi_{A \backslash B}}{ \chi_{B \backslash A}}.$$

If you compute these polynomials in non-zero points (for example, greater than $n$), then you obtain $2 \cdot k$ equations of the form
$$
\chi_{A \backslash B}(x_i) \cdot b_i = \chi_{B \backslash A} \cdot a_i,
$$
where $a_i$ and $b_i$ are corresponding values of $\chi_A$ and $\chi_B$ at $x_i$.

System of $2k$ equations with $2k$ variables over field $\mathbb{F}_p$ can be easily solved. The last thing is to factorize polynomials. The authors provide easy algorithm for this case.

Turning back to your first question $\chi_{\bar S}(x)$ can be expressed with your $s_i$'s for $i$ from $0$ to $k$.


Is there a logic without induction that captures much of P? The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of ordered structures.  The fixed-point operator can be either least fixed-point (as considered by Immerman and by Vardi), or inflationary fixed-point.  (Stephan Kreutzer, Expressive equivalence of least and inflationary fixed-point logic, Annals of Pure and Applied Logic 130 61–78, 2004).

Yuri Gurevich conjectured that there is no logic capturing PTIME (Logic and the Challenge of Computer Science, in Current Trends in Theoretical Computer Science, ed. Egon Boerger, 1–57, Computer Science Press, 1988), while Martin Grohe has stated he is less sure (The Quest for a Logic Capturing PTIME, FOCS 2008).

The fixed-point operator is meant to capture the power of recursion.  Fixed-points are powerful, but it isn't obvious to me that they are necessary.

  Is there an operator X that is not based on fixed-points, such that FOL+X captures a (large) fragment of PTIME?

Edit: As far as I understand, linear logic can only express statements about structures that have quite restrictive form.  I would ideally like to see a reference to, or a sketch of, a logic that can express properties of arbitrary sets of relational structures, while still avoiding fixed points.  If I am wrong about the expressive power of linear logic then a pointer or hint would be welcome.

You want to have a look at what some people call Grädel's Theorem. You can find it in Papadimitriou's book "Computational Complexity" (it's Theorem 8.4 in page 176) or in Grädel's original paper.

In a nutshell, Grädel's Theorem is to P what Fagin's Theorem is to NP. It states that on the class of finite structures with a successor relation, the collection of polynomial-time decidable properties coincides with those expressible in the Horn-fragment of existential second-order logic. These are the sentences of second-order logic of the form
$$
(\exists R)(\forall x)(\phi)
$$
where $R$ is a sequence of second-order relation variables, $x$ is a sequence of first-order variables, and $\phi$ is a quantifier-free formula that, when written in CNF form, is a conjunction of $R$-Horn clauses (i.e. clauses that have at most one non-negated atom involving the variables in $R$).


An extension to the student/college admissions Gale-Shapley algorithm The Gale-Shapley algorithm is an established algorithm that finds an optimal one-to-one match between two groups, each individual of which has a preference for the individuals in the other group (the "stable marriage market problem"). The algorithm has been further extended for one-to-many matchings, often called the college admissions problem. In this example, applicants with preferences for certain colleges are optimally matched with colleges that have preferences over applicants and that also have a certain number of vacancies to fill that can be more than one.
Are there further extensions to this algorithm to optimally match many-to-many relationships?. For illustration, I would like to match projects to sources of funds, where a project might receive funding from multiple sources; and a source of funding may be able to fund more than one project. To use the college admissions analogy, this would be the same as specifying a student to attend one or more colleges whilst a college may accept one or more students.
A further extension of this concept would be to encode inclusivities (e.g., fund A must always be used with fund B), exclusivities (e.g., if project A is funded then project B must not be funded), but these added complexities first need the many-to-many algorithm described above.

I am unsure about matchings of many to many as I haven't seen much of that in the literature but for your extension of exclusivity you may want to look at matching with incomplete lists. This changes the definition of a blocking pair such that they must also find each other acceptable. You could use that to set an agent with only one other agent in its preference list, the result of this would have the agent be unmatched or matched with the agent it ranks. Maybe if many companies can be assigned to one project you could consider this an adaptation of Stable Roommates problem? Where the room is the project and the companies are the people that occupy it. If you want to look further into this I suggest you research:
Stable Matching with incomplete lists (SMI)
Stable Roommates (SR)
Stable roomates with incomplete lists (SRI)
Best of luck!


Why should we believe that $NEXP \not \subset P/poly$ I am sorry if this is not an advanced question. Most computer scientists believed that $NEXP \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used is derandomization and they believe that $P=BPP$ and I know Nissan and Wigderson's generator which exist if $EXP \not \subset P/poly$($E \not \subset Size(2^{o(n))}$). On the other hand, I see some theorems like IP = PSPACE which thought to be false. Recently I read the IKW and there is a theorem states that $NEXP \in P/poly$ then there is a polynomial witness description for any language in $NEXP$. For me, it is likely to happen for example Succinct-HC is an $NEXP$-Complete language and it is likely to have a succinct witness. On the other hand, there are undecidable problems in P/poly that we don't know, maybe we could use them as an oracle to solve Succicnt-HC, They are some reasons in IKW's paper but I need more references that help me to understand why should we believe that $NEXP \not \subset P/poly$.

The best evidence is in my opinion follows due to the results of Ryan Williams on even a mild speed up of $CIRCUITSAT$ provides $NQP\not\subset P/poly$ which is an extremely strong result compared to $NEXP\not\subset P/poly$. It indicates to me that either we are missing something trivial which would separate $NEXP$ from $P/poly$ or (remotely plausibly) anything that separates $NEXP$ from $P/poly$ would separate any class slightly bigger than $NP$ from $P/poly$.
Update It seems all the more likely if we do not reach $NEXP\not\subset P/poly$ by speeding up GapCircuitSAT or CircuitSAT problems we might achieve a separation via embedding $NP$ problems in $MCSP$ in $PTIME$ or $LOGSPACE$. It is unclear if speeding up $SAT$ has anything to do with embedding or vice versa. Please refer Comparing SAT to MCSP reduction class separations and faster SAT class separations?.


Kleene closure of DFA Given an $n$-state DFA (over a binary or any fixed alphabet), what is the complexity of computing its Kleene closure DFA? What is the largest possible/known blow-up in the number of states?

You asked a similar question some time ago about concatenation.  I gave the references back then and they still apply here.    See Yu, Zhuang, and K. Salomaa in their paper, "The state complexities of some basic operations on regular languages", TCS 125 (1994), 315-328, where the state blow-up for Kleene * is described in detail; it is exponential in the worst-case for languages over 2-letter alphabets or larger, with a bound of the form $3 \cdot 2^{n-2}$.  The result for Kleene * was also published (without proof) by Maslov in Dokl. Akad. Nauk SSSR (1970) (and in English in the translation journal Soviet Math. Dokl.)

Evidently the complexity of actually computing the DFA could be exponential in the worst-case, too, then.


SAT in some DTIME always via a constructive proof? Why can the statement $SAT \in DTIME(n^3)$ not be proven through a non-constructive proof? Intuitively a proof would be a turing machine, which solves this problem in $DTIME(n^3)$, but there are non-constructive proofs like the following:
https://cs.stackexchange.com/questions/367/how-can-it-be-decidable-whether-pi-has-some-sequence-of-digits

I would like to elaborate on Kaveh's answer because I see people wondering about the constructive status of $P = NP$.

Levin's algorithm performs a dove-tailing parallel execution of all Turing machines on the given SAT instance. If and when any machine terminates, it is verified whether its output is a solution to the SAT instance. If so, Levin's algorithm terminates, otherwise it keeps going.

The algorithm solves SAT because there is a Turing macine that solves SAT, and so eventually Levin's algorithm emulates enough of it to find a solution. Moreover, with careful programming the dove-tailing technique incures at most a polynomial slowdown of any particular simulated machine, so if there is a machine solving SAT in polynomial time, then Levin's algorithm does it in polynomial time as well.

Now let us consider the logical complexity of the statement *"Levin's algorithm runs in polynomial time". It is a specific algorithm whose Gödel code is some number $\ell$. The statement that it runs in polytime can be expressed in first-order arithmetic using Kleene's predicate $T$:
$$\exists C, k. \forall m . \exists n < 2^{C \cdot m^k}. T(\ell, k, n).$$
This can be read as: "There are $C$ and $k$ such that for every (Gödel code of a) SAT instance $m$ there is (a Gödel code of) an execution trace $n$ of $\ell$ running on input $k$, and the length of execution trace does not exceed $C \cdot m^k$."

The predicate $T$ is primitive recursive, and so is the inner formula as its quantifier is bounded by a primitive recursive function. If I am not making a mistake here (please correct me if I am, or provide a reference as I cannot be the first person noticing this), this means that we can express $P = NP$ as a $\Sigma^0_2$-formula. Thus, by negating the formula we can express $P \neq NP$ as a $\Pi^0_2$-formula. By Friedman's conservativity result we therefore have

  If Peano arithmetic proves $P \neq NP$ then Heyting arithmetic proves $P \neq NP$.

In other words, this shows that in the context of first-order arithmetic $P \neq NP$ has a constructive proof if it has a classical one.

Am I making a mistake somewhere?


How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction? The following question was first presented in MATHEMATICS of StackExchange. With a simple description at first sight, it has far-reaching consequences on plenty of recent and advanced theories, such as Knowledge and Common Knowledge in game theory, logic, and distributed computing. With many excellent answers from MATHEMATICS (with my gratitude), it is still somewhat mysterious to me. So, I am here for more illumination.

Below is the original source from MATHEMATICS for your convenience.

Hua Luogeng (in Chinese, 华罗庚) took a hat-guessing puzzle as an illustration in a booklet focusing on mathematical induction. The following description is a literal translation from Chinese.

  Hat-Guessing Puzzle: A teacher wants to identify the most smartest one from his three students by the following methods: 5 hats are shown, in which 3 of them are white and the other two are black, to the three students. With eyes closed, each student is put on a white hat, while the other two black ones are hidden. Once the permissions of opening eyes are granted, the three students open their eyes simultaneously and are allowed to look at the hats of others without any communication. After a hesitation, they say that "the hat on my own hat is white" with one voice. The question is how do they make it?

The puzzle can be easily generalized to the version with $n$ persons, $n-1$ black hats, and $\ge n$ white hats and be solved by induction on $n$:

When $n$ is 2, the situation is trivial because there is only one black hat. If I am wearing the black one, then the other person can tell that the hat on his head is white, without any hesitation. However, he does hesitate. Contradiction.
Suppose that we have solved the puzzle with $n = k$.
When $n = k + 1$, the reason goes in the following way: If someone is wearing the black hat, all the other people will know that and the problem is reduced to a version with $k$ person, $k-1$ black hats and $\ge k+1$ white hats. According to the inductive hypothesis, the $k$ persons should tell that the hats on their heads are all white, without any hesitation. Contradiction.

While both the puzzle and proof sound very simple, I am very confused with the informal keyword "hesitation" in them. I even cannot tell the vagueness of hesitation clearly. For example, is the hesitation itself a suitable object which can be used in mathematical induction? Informally, my problem can be stated as follows.

  My Problem: How to formally model the hesitation in the hat-guessing puzzle?

Now, I will give an account of my confusion (after the discussion with MATHEMATICS users).

Is it suitable to model the hesitation in terms of rounds? Just like the Muddy Children Puzzle, the teacher can broadcast the following question over and over: What is the color of your hat? If the modeling is OK, is it still on the right way to prove the following statement (for the version with $n$ students) "in the first $n−1$ rounds they all say I don't know, and in the $n$th round, they all say it is white simultaneously"?
I think the statement "If someone is wearing the black hat" given in the original proof is based on the unjustified assumption about the first $n−1$ rounds. In other words, is it necessary to prove first "in the first $n-1$ rounds they all say I don't know", before proving the thing in the $n$th round? If it is, how to prove the $n-1$ part?

Thank you very much for any suggestions.

This isn't really an answer to your questions, but I think it would help in understanding the problem (or the way to answer your questions is) to write out a formal statement and proof of the solution. The proof you've presented doesn't say what is being proven, and as written is certainly incorrect. It states (final bullet point) that the inductive hypothesis is that $k$ people with $k-1$ black hats and $> k$ white hats can tell that they all have white hats without any hesistation, but it proves that $k+1$ people with $(k, >k+1)$ hats can tell with hesitation.

Writing out a more formal proof would also make it clear what modeling assumptions you require for it to work. For example, you would probably end up needing to prove "$k$ people with $(k-1,>k)$ hats can all tell if they have white hats after $k$ moments of hesistation". If so, that means you would need some formal, common-knowledge notion of "moment of hesitation".

I hope that helps a little bit with question #1. (Also, the answers at math.stackexchange seem very good on this topic as well....) It might also help with #2, but I'm not sure what exactly you're asking -- I think the proof by induction would take care of this?


PromiseBQP and expectation values of operators This question is regarding The Equivalence of Searching and Sampling by Aaronson. In page 4 he makes the following statement,

  ... a difficult and unsolved meta-question is whether PromiseBPP = PromiseBQP
  implies SampP = SampBQP. Translated into “physics language,” the question is this: suppose we
  had an efficient classical algorithm to estimate the expectation value of any observable in quantum
  mechanics. Would that imply an efficient classical algorithm to simulate any quantum experiment,
  in the sense of sampling from a probability distribution close to the one quantum mechanics predicts?

I have trouble understanding this statement. From the definition of PromiseBQP I don't see how PromiseBPP = PromiseBQP means an efficient classical algorithm to estimate the expectation value of any observable in quantum mechanics. Any ideas how this connection can be made?

Aaronson is working within a particular context, but if you take his statement in an absolute sense, you're right to be skeptical.

  Translated into “physics language,” the question is this: suppose we had an efficient classical algorithm to estimate the expectation value of any observable in quantum mechanics.

This is technically imprecise. PromiseBQP and BQP, as you no doubt understand, are concerned with sampling states that are constructed with polynomial-sized (uniform families of) circuits. And it's true that if you're talking about 'estimating the expectation value of any observable',  this seems to include ANY quantum state which may generally require an exponential number of gates to construct.

However, the concerns of a complexity theorist preclude much worrying about such 'exponentially' constructable quantum states. In any 'quantum experiment,' if a state evolves from a particular pure quantum state in a set amount of time t, the expectation value of its observables will be very close to some state that can be constructed from a circuit with a polynomial number of gates.

That is, the complexity theorist paradigm of 'experiments deal with polynomial time constructable states' is realistic for experimental physics in all contexts that I'm familiar with.


NP-complete variants of NPI problems Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that increase the hardness of problems in $NPI$ from an intermediate complexity to full $NP$-completeness. I'm interested in other $NP$-complete variants of $NPI$ problems. Ideally, a recent survey paper of $NP$-complete variants of $NPI$ problems would be the best answer?

EDIT July 1st, 2012 The bounty will be awarded to the person that lists the maximum number of such problems.

From Papadimitriou's paper "On total functions, existence, theorems and computational complexity":

Nondeterministic multivalued functions with values that
are polynomially verifiable and guranteed to exist form an
interesting class (called $TFNP$) between P and NP ...

.... It is quite interesting, in view of Theorem 2.1,
that in some cases of problems in $TFNP$, if together with the input
we are also given one of the solutions
that are guaranteed to exist, then the problem indeed becomes NP-complete ...

For example the TRICHROMATIC TRIANGLE problem is in $TFNP$, but the SECOND TRICHROMATIC TRIANGLE is $NPC$ (the paper contains a sketch of the proof).


A few questions about Object-Oriented Languages in general I was not a big fan of Object-Oriented Languages (OOL), but recently started to learn a bit more about their pros and cons in a general setting instead of diving into one such language.  I have a few questions here:

Do methods in an OOL contain free variables?  If they do, are they statically-scoped?
Do method names live in a different name space than variables?

For both questions, I have kinda guess answers but am not quite sure.  However, I would like to know more about the reasons behind and consequences of OOLs' specific answers to these questions.

The answers to these questions vary with the specific OO language. Here are some fairly generic answers.

Can methods contain free variables?
In general yes.

Are free variables statically-scoped?
It's complicated. As a general rule (with many exceptions), most variables are lexically-scoped, except that the self reference (e.g., this in Java) is  an implicit, dynamically-scoped variable. Many OO languages further rewrite function calls m() to a method invocation this.m() if m is known to be a method of the type of this.

Do method names live in a different name space than variables?
Yes. Method names are not variables: they may not be freely $\alpha$-renamed, since the actual text of the name constitutes part of the interface of an object. They are much more closely related to record labels or module component names. However, method names can interact with binding structure since many OO languages treat method invocations a bit specially (e.g., my answer to #2).


How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense? Note: This has been cross-posted to Quantum Computing SE.

If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the Extended Church Turing thesis. However, in a related thread, a user raised the objection that the random circuit sampling problem might not be a computation in the Church Turing sense:

  @glS: Decision problems, computable functions, etc. are equivalent, so whichever form you like. Sampling is not even a function, much less a computable one. It's a physical process outside the scope of computing/functions.

Could someone elaborate on this apparent discrepancy? Can the random circuit sampling problem indeed be framed in terms of computable functions and effective calculability or a decision problem, as the CT thesis requires?

Answer from the other SE site

The Church-Turing thesis is not in and of itself a rigorous concept, but rather a judgment on rigorous concepts of computability. As such, it's negotiable. The language in Rosser's 1939 expository paper about provability and computability is biased towards deterministic algorithms. There is an important simplifying theorem here: If you only care about what is ever computable, then you don't need randomness or quantum randomness, because you can simulate them using exponentially more time. Like many simplifying results, it can be taken in the wrong way. It meant that in the 1930s, back when mainly logicians were defining what was computable at all, randomized algorithms were not yet on their radar.

If you extend your thinking to the Extended Church-Turing thesis, then you should also extend your scope to randomized computation. You have no choice, because even if an algorithm answers a deterministic question (like whether a number is prime), the method of calculation could be randomized (like Miller-Rabin or ECPP). And then it's not very natural to demand that the answer be deterministic even if the solution doesn't have to be.

On the other hand, you're free to be a stickler in your personal interpretation of ECT, because it's not a rigorous concept. You're free to say that Google's quantum supremacy gets a bronze medal in its fight against ECT, but not a gold medal, because it doesn't answer a deterministic question.

Or you could be even more of a stickler and say that none of this counts because quantum computing isn't deterministic. Then I would say that I believe this reactionary version ECT after all --- a TM with a linear tape is polynomially equivalent to one with a 2D tape, etc. But I would also say that that's not the right question.


Dependences imposed on Subset Sum Problem Given a set of $n$ positive integer variables, namely $S=\{ s_1, s_2, \cdots, s_n\}$. Find a subset $A \subseteq S$, so that $\Sigma_{s_i \in A} s_i = K$. $K$ is a given parameter.

Unlike the usual one, there is a dependence constraint set here, $D=\{ (a_1, b_1), \cdots, (a_m, b_m) \}$. Here $(a_i, b_i)$ means $a_i \in A$ implies $b_i \in A$. Furthermore, the dependence is not circular. Put another way, if we represent $D$ as a directed graph $G'(V, E)$, that nodes in $G$ corresponds to variable in $S$ and $(a,b) \in D$ iff $(a,b) \in E$, then $G$ is a DAG (acyclic digraph).

Note: Pseudo-polynomial time in terms of $\Sigma_{s \in S} s$ is acceptable for my problem.

I have proved this problem as strongly NP-complete via a reduction from CLIQUE.

  Question. I am looking forward to an algorithm that finds a subset $A$ so that $\Sigma_{s_i \in A} s_i$ lies in a neighbourhood of $K$, e.g., between $(1-\alpha)*K$ and $(1+\alpha)*K$.

Thank you very much for your comment and answer. :) Any reference concerning is welcome.

Special case solved: When each variable is implied by at most one another variable, i.e., $\forall_{b \in S}$, $|\{(a,b) \in D \}| \le 1$, it could be solved by DP in $O(n*M*M)$. $M=\Sigma_{s_i \in S} s_i$.

This is not a solution, but a reference suggestion.

The problem should be (a special case of the decision version of) the partially-ordered knapsack problem.  For example, you can look at the following paper and the references therein.

S.G. Kolliopoulos and G. Steiner: Partially ordered knapsack and applications to scheduling. Discrete Applied Mathematics 155 (2007) 889-897.  http://dx.doi.org/10.1016/j.dam.2006.08.006


Should one study undergrad TCS materials before taking grad-level ones? (soft question) I am a 1st year PhD student. I got a bachelor's degree in CS but I didn't start learning TCS systematically until this year.
This dumb question came to me when I opened an undergrad complexity lecture watchlist after I forgot it for months, and realized that I had already learned the content from an "advanced" textbook. And I found things covered by the course were learned by myself within a much shorter time. That's perhaps a special case. But I noticed that undergraduate-level courses/materials cover more details and examples about the basic concepts than advanced ones, and I don't know if it's necessary to know such a kind of details.
So my real question starts here: should one skip undergraduate-level TCS courses/materials to save time, or do it step by step to reinforce knowledge?

Yes.
From my experience, going back to basics teaches you new things every time.
My students tough me the most.


Is the problem "MIN-SET-PARTITION" an NP-hard problem? Given a family of sets $F = S_1, ..., S_n$ of elements from a universe $U$, find the minimal integer $k$ for which there is a partition of $F$ of size $k$, such that every two sets in the same partition are disjoint. Formally, we want $P_1, ..., P_k$ such that for every $1 \leq i,j \leq k$, we have $P_i \subseteq F$ and $P_i \cap P_j = \emptyset$. Furthermore, for every $S,T \in P_i$ we have $S \cap T = \emptyset$. Finally, $\bigcup P_i = F$.

We can ask the same question as a decision problem: $\lbrace U,F,k \rbrace \in MIN-SET-PARTITION$ iff there is a partition (as described above) of $F$ of size $k$.

My intuition is that this is indeed NP-hard and that someone has probably already thought about it. I'd be happy to get a reference or a description of a reduction.

Thanks!

Take $S_i$ to be the edges of a graph $G$. Then, a partition $F$ of size $k$ corresponds to an edge-coloring of $G$; the minimum such $k$ corresponds to the chromatic index of $G$. Edge-coloring is known to be NP-complete: "The NP-Completeness of Edge-Colouring".


Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “Consequences of Faster Alignment of Sequences” by
Abboud, Vassilevska Williams, and Weimann available [here][1]. The term of a certain size in the title of this question refers to the support set being $\{-n^3,\ldots,n^3\}$:
Conjecture 1 (3-SUM Conjecture) In the Word RAM model with words of $O(\log n)$ bits, any algorithm requires $n^{2−o(1)}$ time in expectation to determine whether three sets
$A,B,C \subset \{−n^3,\ldots,n^3\}$ with $|A| = |B| = |C| = n$
integers contain three elements $a∈A,b∈B,c∈C$ with $a+b+c=0.$
If there was an algorithm solving this exact version of 3SUM with complexity $O(n^{2-\varepsilon})$ for $\varepsilon>0,$ what would be the impact on the Exponential Time Hypothesis?
Again, not being an expert, I am wondering would the ETH be refuted? Or the strong ETH only? Please feel free to include details that may be "obvious" in your comments and answers.

I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time algorithms (at least via Karp reductions) because it would only improve constants in the exponent of the runtime. In particular, if we reduce 3-SAT to a 3SUM instance of size $2^{O(n)}$, it will not refute ETH, and if we reduce 3-SAT to a 3SUM instance of size $2^{o(n)}$, it will refute ETH regardless of the complexity of 3SUM.
[1] Virginia V. Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). IPEC 2015. https://drops.dagstuhl.de/opus/volltexte/2015/5568/pdf/5.pdf


Is there a proof that addition is faster than multiplication? The best upper bound known on the time complexity of multiplication is Martin Fürer's bound $n\log n2^{O(\log^* n)}$, which is more than linear time complexity of addition.  Do we have a proof that addition is inherently easier than multiplication?

No.

No unconditional better lower bound than the trivial $\Omega(n)$ is currently known for integer multiplication. There are some conditional lower bounds though. For more on this, you can have a look at Martin Fürer's paper Faster Integer Multiplication.

Edit following Andrej's comment: Addition can be done in time $\mathcal O(n)$. In comparison, the best known upper bound for multiplication is (approximately) $\mathcal O(n\log n)$. On the other hand, no non trivial lower bound is known for multiplication, thus there is no proof that addition is faster than multiplication yet. As (too) often in complexity theory, we just don't know!


A decision problem which is not known to be in PH but will be in P if P=NP Edit: As Ravi Boppana correctly pointed out in his answer and Scott Aaronson also added another example in his answer, the answer to this question turned out to be “yes” in a way which I had not expected at all.  First I thought that they did not answer the question I had wanted to ask, but after some thinking, these constructions answer at least one of the questions I wanted to ask, that is, “Is there any way to prove a conditional result ‘P=NP ⇒ L∈P’ without proving the unconditional result L∈PH?”  Thanks, Ravi and Scott!

Is there a decision problem L such that the following conditions are both satisfied?

L is not known to be in the polynomial hierarchy.
It is known that P=NP will imply L∈P.

An artificial example is as good as a natural one.  Also, although I use the letter “L,” it can be a promise problem instead of a language if it helps.

Background.  If we know that a decision problem L is in the polynomial hierarchy, then we know that “P=NP ⇒ L∈P.”  The intent of the question is to ask whether the converse holds.  If a language L satisfying the above two conditions exists, then it can be thought of as an evidence that the converse fails.

The question has been motivated by Joe Fitzsimons’s interesting comment to my answer to Walter Bishop’s question “Consequences of #P = FP.”

If an artificial example is really as good as a natural one, then I can indeed provide such an example!

Edit: Furthermore, my example is "somewhat" less of a cheat than the one suggested by Ravi Boppana (where we take L to be the empty language if P = NP and the halting problem otherwise), in that I'll define the language L by giving a finite procedure to decide whether $x \in$ L for any input x.  At no point will deciding whether x∈L require solving an "unbounded" mathematical question such as P vs. NP.

Without further ado: let $M_1, M_2, ...$ be an enumeration of polytime Turing machines.  For all $n$, let $M_{t(n)}$ be the lexicographically first $M_i$ that correctly decides 3SAT on all inputs of length $n$ or less.  Then define the language L as follows: for all inputs $x$ of size $n$, $x \in$ L if and only if the Turing machine encoded by $x$ halts in at most $n^{t(n)}$ steps when run on a blank tape.

Claim 1: If P = NP, then L $\in$ P.

Proof: If P = NP, then there's some fixed $M_i$ that solves 3SAT for all inputs; hence $t(n) \le i$ for all $n$. QED

Claim 2: If P $\ne$ NP, then L $\notin$ P.

Proof: If $t(n)$ increases without bound, then we can simply apply the Time Hierarchy Theorem. QED

Now, not only is L not in P assuming P $\ne$ NP: one presumes it wouldn't be in PH (or even PSPACE) either!

Incidentally, I wonder if anyone can improve the above construction, to get a language L which is in P if P = NP, but provably not in PH or PSPACE if P $\ne$ NP?


Translating HORNSAT to SAT, revisited See Translating SAT to HornSAT

It says in that post that it is impossible to translate SAT into HORNSAT. But it is known that HORNSAT is P-complete, so any language in P can be translated into HORNSAT. Then if it is impossible to translate SAT, which is in NP, into HORNSAT, then wouldn't this imply that P is not NP? What am I missing?

That question was about a translation from an arbitrary instance of SAT to a HORN-SAT instance with the exact same satisfying assignments. The translation property needed for P$\neq$NP is just equisatisfiability, not equality of assignments. That is, it simply requires them both to be satisfiable, or unsatisfiable. If satisfiable, they may be satisfied by different assignments.

For example:
$a \wedge \neg b$ and $\neg a \wedge b$ are equisatisfiable (they are both satisfiable), but they have different satisfying assignments.

The answer was that there can not be a satisfying assignment preserving translation, but this doesn't tell us whether there is a polynomial time satisfiability preserving translation.


Ref question: K-nearest neighbours in a graph Given an undirected  graph $G$  with $n$ vertices,  $m$ edges, and positive weights on the edges, I am interested in the problem of computing for each vertex the $k$ distinct vertices in $G$ that are closest to it on the shortest-path distances in $G$. There is a solution that follows by modifying Dijkstra, where the running time is $k$ times the running time of the standard Dijkstra. Anybody knows a ref to this result? Should I bother to write this down?

thanks....

Update: I wrote down my algorithm in case anybody is interested...
http://sarielhp.org/p/14/k_nn/

In Victor Teixeira de Almeida, Ralf Hartmut Güting: Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases. SAC 2006: 58-62, Teixeira and Güting describe a new storage schema with a set of indexed structures to support an efficient
execution of a slightly modified version of the Dijkstra's algorithm.

In the introduction they simply use the reference to the original Dijkstra's paper:

... An obvious modification on Dijkstra's algorithm
[reference to the original Dijkstra's 1967 paper] that computes shortest path between objects could be done in order to compute the k-NN using the network space.
But, in this case, sepcial storage schemas are necessary in order to
efficiently support this algorithm. In this paper, ...

So I think you can use the same approach: if your work is NOT focused on a new variant of a k-NN algorithm you can simply mention it and cite Dijkstra's paper; otherwise you should also include other references on the subject; I think there are many of them because the k-NN problem is important, for example, in navigation systems; googling around I found: Fast Nearest Neighbor Search on Road Networks, Alternative Solutions for Continuous K-NN Queries in Spatial Network Databases, ...


Algorithms for finding all cliques of a given degree in a graph Consider a graph with $n$ vertices and maximum degree $Δ$. I would like to obtain all $s$ cliques, where $s≤Δ$ and both of them are small compared to $n$.

Bron-Kerbosch algorithm gives all maximal cliques but that's not quite what I need. I want all s cliques (where $s≤Δ$), including not maximal ones.

Are there any efficient algorithms to do this? Even achieving an exponential speed-up would be good?

This maybe: https://papers-gamma.link/paper/32
With an open source implementation here: https://github.com/maxdan94/kClist


Natural computation based on fundamental forces Well-known examples of computation inspired by natural phenomenon are quantum computers and DNA computers.

What is known about the potential and/or limitations of computing with Maxwell's laws or gravity?

That is, incorporating nature's "quick" solutions to Maxwell's equations or the n-body problem directly into a general-purpose algorithm?

At present, quantum computation is the most powerful of computational model based on known physics to have been experimentally realised, and can efficiently simulate Maxwell's equations, and pretty much every other physical phenomenon you encounter in day to day life. As the others have mentioned, one exception to this is general spacetimes allowed as solutions in general relativity.

There has been quite a lot of interest in the computational power of computers with access to closed time like curves, for example. However there is absolutely no evidence that these exist in nature or that they can be created artificially. So, while there are potentially interesting computational models that incorporate general relativity in some form, there is significant doubt over whether such models can be realised, and before we can have the most general model of physical computation we need a solid theory of quantum gravity.

Further the interesting features of general relativity tend to only show up in regions of high curvature, which is very different from the almost flat region of spacetime we inhabit and the effects of relativity in such flat(ish) space offer no computational advantage.


Finding witness in minkowski sum of integers Let $A$ and $B$ be subsets of $\{0,\ldots,n\}$. We are interested in finding the Minkowski sum $A+B=\{a+b~|~a\in A,b\in B\}$.

$\chi_X:\{0,\ldots,2n\}\to \{0,1\}$ is a characteristic function of $X$ if $$\chi_X(x) = \begin{cases} 1 \text{ if } x\in X\\ 0 \text{ otherwise}\end{cases}$$

Let $f$ be the discrete convolution of $\chi_A$ and $\chi_B$, then $x\in A+B$ if and only if $f(x)> 0$. Hence $A+B$ can be computed in $O(n\log n)$ time by discrete convolution via FFT.

Sometimes it is important to find out the actual pair $a\in A$ and $b\in B$ that sums to $x$. $a\in A$ is called a witness of $x$, if there exist $b\in B$ such that $a+b=x$. A function $w:A+B\to A$ is called a witness function if $w(x)$ is a witness of $x$.

  Is it possible to compute a witness function in $O(n\log n)$ time?

Ok, I've been holding off since really Sariel should get credit for an answer, but I'm tired of waiting, so here is my cut at a near-linear randomized algorithm.

By choosing samples of $n(1-\epsilon)^i$ points, $i=0,1,\dots$, you can get a logarithmic number of subproblems such that each sum from the original problem has constant probability of being represented uniquely in one of the subproblems (the one where the sampling cuts down the expected number of representations to near 1).
By repeating the sampling process a logarithmic number of times you can get all sums to have unique representations with high probability.
If you have a partition of $A$ and $B$ into two subsets, then by multiplying the numbers by four, adding 2 to the numbers in one of the subsets in $A$, and adding 1 to the numbers in one of the subsets in $B$, you can read off from the mod-4 values of the achievable sums which of the two subsets their summands come from.
By repeating the partition process a logarithmic number of times, using each bit position of the binary representations of the values or indices in the subproblems to select the partitions in each step, you can uniquely identify the summands of every uniquely-represented sum.

This blows up the running time by three logarithmic factors; probably that can be reduced.


Basic property of boolean functions with restrictions For $f:\{\pm1\}^n\to\mathbb{R}$, $I\subset\{1,\dots,n\}$ and $x\in\{\pm1\}^{\{1,\dots,n\}\setminus I}$ we define $f_I[x]:\{\pm1\}^I\to\mathbb{R}$ by $f_I[x](y)=f(x,y)$. (We denote by ($x,y$) the assignment to all $n$ variables given by $x$ and $y$.)

Let $S\subseteq I$. I have proved that $\mathbb{E}_x\left[\widehat{f_I[x]}(S)\right]=\widehat{f}(S)$, where $\widehat{f}(S)$ is the Fourier coefficient of $f$ corresponding to $S$. Now I want to show (possibly using the first result) that
$$\mathbb{E}_x\left[\widehat{f_I[x]}^2(S)\right]=\sum\limits_{T:T\cap I=S}\widehat{f}^2(T).$$

Any useful ideas would be greatly appreciated.

This is Corollary 3.22 of Analysis of Boolean Functions, by Ryan O'Donnell (2014). You may want to consult the proof in the book, or look directly at the online version (which has a different numbering: this corresponds to Corollary 22 there).

Note that you can obtain a version of the book following this link.


Generalizing Parsing Expression Grammar for Context Sensitive Grammars One of the things I like about parsing expression grammars is that they're automatically unambiguous, and unambiguity is a very important property to have. However, context-free grammars are somewhat weak. Is there a generalization of parsing expression grammars that works for context-sensitive grammars? What I mean by that is whether there exist a generalization such that

the generalization allows for nonterminal symbols to be on both sides of the production rule.
the generalization preserves the property that an unambiguous parse is always produced.

PEGs are unambiguous exactly because at each choice point, i.e, alternatives of a grammar rule, you can choose one and never change it. Context-free grammars, or to be more precise general parsing algorithms like Early or GLR, explore all the alternatives which can lead to ambiguity.

We have to also distinguish between ambiguity and non-determinism. PEGs reduce non-determinism at runtime, which guarantee at most one parse result, but at the same time, they can lead to parse errors even when there is no ambiguity. For example, consider the grammar:

A ::= 'a'
    | 'a' 'b'

and the input 'ab'. This will lead to a parse error because the parser made a premature choice. This is the main shortcoming of PEGs.

About general parsing algorithms, it is not possible to guarantee un-ambiguousness, but at the same time guarantee that the correct (intended) parse tree is returned. There are many disambiguation techniques that try to reduce non-determinism at runtime, and as a result remove ambiguities, but there no guarantee. The underlying grammar may be ambiguous.

What do you mean by context-sensitive grammars? Something like Python that has indentation-sensitivity? If you are looking for such features, the answer to your first question is yes. You can take a look into monadic parser combinators (with limited backtracking). They are essentially PEGs and allow threading of values into the parsing state to simulate context-sensitiveness. I am not aware of any formalism that allows you to write arbitrary context-sensitive grammars with more than one nonterminal on the left-hand side.

The answer to the second question is also yes. If you always select one alternative and never backtrack, you will get at most one parse tree, but it may not be the one you want or you can get a parse error.

You can also look into one of my previous work on data-dependent GLL Parsing where we describe how to deal with context-sensitivity in general parsing. The paper has a good discussion (IMO) of different parsing techniques.


How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph? I am not a computer science theorist, but think this real world problem belongs here.

The problem

My company have several units accross the country.

We offered to employees the possibility to work on another unit. But there is a condition: The total number of workers on a unit cannot change.

That means: We'll allow a employee to left his unit if someone wants his place.

Example (ficticious) request data:

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

The above, plotted:

See how we have to choose between the red, blue or black options?

The real problem is a little more complex, because we have 27 units and 751 requests. Please take a look at the visualization

The goal

Having collected all the requests, how to satisfy most of them?

Theory(?) application

Having graph $G(V, E)$, let every unit be a vertex $V$ and a request be a directed edge $E$, a successful exchange will take the form of a directed cyle.

Each cycle must use $E$ only once (a worker cannot leave his unit twice), but can visit $V$ several times (a unit can have many workers wanting to leave).

The question

If this problem is expressed as

  "How to find the cycles which, together, involve the biggest number of
  non-shared edges in a directed graph"?

Will we satisfy most of the requesters?

That being true, there is an algorithm to find that optimal set of cycles?

Will this greddy approach solve the problem?

Find the biggest directed cycle on $G$;
Remove it's edges from $G$;
Repeat 1 until there is not a directed cycle on $G$;

Can you help me?

Do you know another way to describe the original problem (making most of requesters happy)?

Edit: changed department to unit, to better describe the problem.

This is a standard minimum-cost circulation problem.  Give each directed edge capacity $1$ and cost $-1$.  Then a feasible circulation is a sum (ie, union) of edge-disjoint directed cycles, and the cost of the circulation is the negation of the number of edges.

Because all the costs and capacities are bounded by constants, a simple cycle-cancelling algorithm will find the required circulation in polynomial time.  This is almost the same as the obvious greedy algorithm:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

Here, the cost of a cycle is the sum of the costs of its edges.  Negative-cost cycles can be found using the Bellman-Ford shortest-path algorithm in $O(VE)$ time.  Each iteration reduces the cost of the current circulation by at least 1.  The initial (empty) circulation has cost $0$, and the final circulation has cost at least $-E$.  Thus, the algorithm ends after at most $E$ iterations, so its total running time is at most $O(VE^2)$.

This is not the fastest algorithm known.


Finding a simple dual of a simple graph in some surface Given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph embedding as vertices and adding an edge between two vertices for every side the corresponding faces have in common in the original graph.

Here's my problem. Given a simple graph $G$, I need to find another simple graph $G'$ such that there exists a surface $S$ and a cellular embedding of $G$ on $S$ such that $G'$ is the dual of this embedding of $G$. Some simple graphs $G$ do not have simple duals on any surface (for example, a simple path; see JɛﬀE's comment). On the other hand, I think that for some simple graphs $G$, there can be many possible simple duals $G'$, depending on the surface and the embedding chosen.

Question: Given a simple graph $G$, give a method that finds a simple dual graph $G'$, if it exists.

None of the embeddings is required to be of minimum genus. The graphs are assumed to be connected.

For 3-regular graphs, having a simple dual is the same thing as having a polyhedral embedding (an embedding in which each face is a simple cycle and every two faces intersect in an empty set, a vertex, or an edge). But testing for the existence of a polyhedral embedding is known to be NP-complete: see B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf

I'm not sure whether polyhedral embeddability is known to remain NP-complete when restricted to 3-regular graphs — it doesn't seem to be in Mohar's paper — but it seems very likely to be true.


Hardness of geometric area minimization problem This question is a generalized variant of: Hardness of perimeter minimization?

Given $xyz=C$ where $x, y,$ and $z$ are integer variables and $C$ is integer constant. Assume all integers are encoded in binary.

  What is the complexity of finding $x, y, z$ such that $xy+xz+yz$ has minimum value? Is there any subexponential algorithm that solves this problem? Does the problem become easier when integers are encoded in unary?

Edit Motivation: I'm interested in the following generalized problem:

Input: intgers $C$ and $K$

Problem: Find integers $x$, $y$, and $z$ such that $xyz\ge C$ and $xy+xz+yz\le K$

Never mind. I misremembered the definition of 3-partition.

I'll leave what I wrote here here, but since division into 3 subsets with equal sums is not strongly NP-complete, this doesn't work.

By 3-subset sum, I mean a: given a set of integers, find a partition into 3 subsets whose sums are all equal.

The problem is roughly equivalent to: let $\{p_i\}$ be the multiset of prime factors of $C$; find the best way of partitioning the multiset $\{r_i\}$ into three parts with equal sums, where $r_i = \log p_i$, for $p_i$.

Here's the wrong argument I had before.

=========================

Find a bunch of primes $p_1$, $p_2$, $\ldots$, $p_{\alpha(n)}$ so that $\log p_i \approx M\ i$ for some real $M$.  Now, take a 3-subset sum problem on integers $1 \ldots \alpha(n)$, and replace the integer $i$ with prime $p_i$. Let $C$  be the product of all the primes $p_i$ corresponding to the integers $i$ in the 3-subset sum problem. Then, any $x$, $y$, $z$ with $x \approx y \approx z$ and $xyz = C$ gives a good partition of the integers in the 3-subset sum problem. Let $p_x$, $p_y$, and $p_z$ be the multisets of primes making up the prime factorization of $x$, $y$, and $z$, respectively. If $x$, $y$, and $z$ are close, $\log x \approx \log y \approx \log z$ means $ \sum_{p_i \in p_x} \log p_i \approx \sum_{p_i \in p_y} \log p_i \approx \sum_{p_i \in p_z} \log p_i$, and so you have a good solution to the 3-subset sum problem (and if you've chosen the primes right, you can tell from the optimal $x$, $y$ and $z$ whether or not the original 3-subset-sum problem is solvable). Since you know what the primes you used were, factoring $x$, $y$ and $z$ can be done by trial division to recover the partition.


Complexity of Determining Linear Separability Be $X := \{x_1,...,x_N\}$ and $Y := \{y_1,...,y_N\}$ subsets of $\mathbb{R}^d$.

What is/are the most efficient existing algorithm/s for determining whether X and Y are linearly separable and what is its/their computational complexity (O notation and P/LP/NP)?

If you merely want separation, then this is solved using linear programming. If you want to maximize the separation, then you're in the land of linear classification problems and max-margin classification in general.


Proofs found by computer In 1996, a long-standing open problem was solved by a computer; namely, that Robbins algebra and Boolean algebra are the same. The proof was found by an automated theorem prover.

Moreover, the known proof of Four color theorem contains computer-generated components.

The aim of this question is to list proofs that are (completely or partially) found by computer (whether the only known proof or the one discovered for the first time).

Another famous example is Hales' proof of Kepler's conjecture which had a very large computer aided component.

From Wikipedia:

  In August 1998 Hales announced that the proof was complete. At that stage it consisted of 250 pages of notes and 3 gigabytes of computer programs, data and results.


How big is the variance of the treewidth of a random graph in G(n,p)? I am trying to find how close $tw(G)$ and $E[tw(G)]$ really are, when $G \in G(n,p=c/n)$
and $c>1$ is a constant not depending on n (so $E[tw(G)] = \Theta(n)$). My estimate is that $tw(G) \leq E[tw(G)] + o(n)$ w.h.p, but i haven't been able to prove it.

You don't need to calculate the variance to prove the concentration of tw(G(n,p)) around its expectation. If two graphs G' and G differ by one vertex then their treewidth differs by at most one. You can use the standard method, the Hoeffding-Azuma inequality applied to the vertex exposure martingale to show, for example,

$\mathbb{P}( | tw(G(n,p)) - \mathbb{E} tw(G(n,p))| > t) \le 3 e^{- t^2/(2 n)}$,

so the above probability tends to 0, if, say $t = n^{0.51}$.

The method was first applied to prove concentration for the chromatic number of $G(n,p)$. See B. Bollobás, Random graphs. Springer New York, 1998, page 298.


Satisfiability for various branching programs Clearly, SAT for CNF, formula, or many classes of boolean circuits have strong significance on the entire theory community.
Branching program, or BDD is one of the most basic and popular computational models for boolean functions. For instance, arbitrary space bounded TM with space $S(n)$ are simulated by  branching program of size $2^{S(n)}$.
My question is about  classification of hardness of $satisfiability$ problem for $branching$ $programs$.
More concretely,

Q1. SAT for branching programs corresponding natural complexity classes like $L/poly$, $NL/poly$, or $\oplus L/poly$ can be computed polynomial time ?
Q2. Is there some $threshold$ $condition$ for BP-SAT problem ? For example, I hope some results as follows: for some two classes of branching programs $\mathcal{C},\mathcal{D}$, one of two is polytime computable and the other one is NP hard.

For Q2:

For Ordered BDDs (OBDD) both satisfiability and counting solutions is polynomial in the size of the OBDD.

For indexed BDD, IBDD p. 16 satisfiability is NP-complete and the equivalence test is coNP-complete even if there are only two layers.

In general if a variable is read more than one time it is NP-complete if I remember correctly.


One Stack, Two Queues background

Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no satisfactory result came up. I remember the course TA insisted on something he couldn't prove, and said he forgot the proof, and ... [you know what].

Today, I recalled the problem. I was still eager to know, so here it is...

The Question

  Is it possible to implement a stack using two queues, so that both PUSH
  and POP operations run in amortized time O(1)? If yes, could you tell
  me how?

Note: The situation is quite easy if we want to implement a queue with two stacks (with corresponding operations ENQUEUE & DEQUEUE). Please observe the difference.

PS: The above problem is not the homework itself. The homework did not require any lower bounds; just an implementation and the running time analysis.

I don't have an actual answer, but here's some evidence that the problem is open:

It's not mentioned in Ming Li, Luc Longpré and Paul M. B. Vitányi, "The power of the queue", Structures 1986, which considers several other closely related simulations
It's not mentioned in Martin Hühne, "On the power of several queues", Theor. Comp. Sci. 1993, a follow-on paper.
It's not mentioned in Holger Petersen, "Stacks versus Deques", COCOON 2001.
Burton Rosenberg, "Fast nondeterministic recognition of context-free languages using two queues", Inform. Proc. Lett. 1998, gives an O(n log n) two-queue algorithm for recognizing any CFL using two queues. But a nondeterministic pushdown automaton can recognize CFLs in linear time. So if there were a simulation of a stack with two queues faster than O(log n) per operation, Rosenberg and his referees should have known about it.


Closure under Minkowski sum. The Minkowski sum of two sets of vectors $A, B \in R^d$ is given by

$$ A \oplus B  = \{ a + b \mid a \in A, b \in B \}$$

I just heard an interesting problem (attributed to Dan Halperin): Given a shape $B$, does there exist a shape $A$ such that $A \oplus A = B$ ?

But that's not my question (it appears to be an open problem). Observe that in the above problem, if $B$ is a convex set, then there exists a solution $A = (1/2)B$ since convex sets are closed under the taking of Minkowski sums.

Fix a class of shapes ${\cal S}$. We say that ${\cal S}$ is closed under Minkowski sums if for any $A, B \in {\cal S}, A \oplus B \in {\cal S}$.

So my question is:

  Is there a nice characterization of
  classes of shapes ${\cal S}$ that are
  closed under Minkowski sums ?

Lattices and linear subspaces are closed under Minkowski sum. Thats more or less immediate from their definition. Lattices+linear subspaces are closed under Minkowski sum (i.e., a member of this set is for example a set of parallel lines in distance 1 from each other). Connected polygons with holes are closed under Minkowski sum. Rings [the set differences of two concentric disks] are closed under Minkowski sum (a disk is considered to be a ring, naturally). The set of line segments parallel to a certain direction are closed under Minkowski sum. Mushed potatoes are closed under Minkowski sum, but only if they are well cooked (or maybe not, it is too late)...

Also, the family of finite union of concentric rings is closed under Minkowski sum.


Quasi-polynomial time algorithm for permutation group isomorphism Is there a known $n^{\alpha \log n+O(1)}$ algorithm for permutation group isomorphism? Here $n$ is the size of the group, and the isomorphism must be a permutational isomorphism.

My hope for such an algorithm comes from reading a blog post on the group isomorphism problem and its comments. Because any group of size $n$ has a generator set of size at most $\log_2 n$, maybe a permutation group will even have a strong generator set of size at most $\log_2 n$ (and hopefully that would already be sufficient for a quasi-polynomial algorithm). The comments mention two papers that relate the complexity of the  problem of permutational isomorphism of permutation groups to the complexity of the problem of isomorphism of semisimple groups, and also mention earlier work on the permutational isomorphism problem.

A comment by Ben Barber on a related question indicates that permutation group isomorphism can be reduced to graph isomorphism, which is not really surprising, but nice to know nevertheless.

The answer is basically yes, if we take into account the hidden assumption that the degree of the group is at most $n$. More precisely, let $G_1, G_2$ with $|G_1|=| G_2|=n$ be finite permutation groups acting on a set $\Omega$. Then existence of a permutational isomorphism between $G_1$ and $G_2$ can be checked in time $n^{\log_2 n} \cdot {\max(|\Omega|,n)}^{O(1)}$.

As suggested in the question, a permutation group has a base and corresponding strong generating set (SGS) of size at most $\log_2 n$, and both can be computed in time polynomial in $n$. But this isn't even needed, any generating set of size at most $\log_2 n$ is enough.

After computing such a generating set for $G_1$, the algorithm simply maps successively each element of the generating set to an element of $G_2$, and checks for each such mapping whether it leads to an isomorphism of $G_1$ and $G_2$. For those who do, the algorithm then checks whether there is a permutation of $\Omega$ inducing that isomorphism (for example by a canonical labeling technique, which is closely related to a similar technique for deterministic finite automata, but more group theoretic methods also work). Those checks can be done in time ${\max(|\Omega|,n)}^{O(1)}$, and because there are at most $n^{\log_2 n}$ such mappings, and every isomorphism between $G_1$ and $G_2$ is determined by such a mapping, the above time bound follows.


How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)? The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about algebraic geometry, and in fact also only have a cursory, undergraduate understanding of the obstacles at play in the P/poly versus NP question (non-relativizing, non-algebrazing, likely won’t be a natural proof).

What makes algebraic geometry seem like it can bypass these sorts of obstacles? Is it just field expert intuition or do we have a really good reason to believe the approach is fundamentally more powerful than previous approachs? What weaker results have this approach been able to achieve?

[I'll answer the question as stated in the title, leaving the litany of other questions about GCT for other threads.] Proving the conjectures arising in GCT seems like it will crucially use the fact that the functions under consideration (determinant and permanent, and other related polynomials for P/poly and NP) are characterized by their symmetries.  This necessity is not a formal result, but an intuition expressed by several experts.  (Basically that in the absence of characterization by symmetries, understanding the algebraic geometry and representation theory that arises is far harder.)

This should bypass Razborov-Rudich because very few functions are characterized by their symmetries (bypassing the largeness condition in the definition of natural proofs).  Again, I have not seen a proof of this, but it is an intuition I have heard expressed by several experts.

Now, over the complex numbers, it's not clear to me that there's an analog of Razborov-Rudich.  Although most of GCT currently focuses on the complex numbers, there are analogs in the finite characteristic (promised in the forthcoming paper GCT VIII).  In finite characteristic, one might actually be able to prove a statement of the form "Very few functions are characterized by their symmetries."

[In response to Ross Snider's comment, here's an explanation of characterization by symmetries.]

First, an explanation-by-example.  For the example, define an auxiliary function $q$.  If $A$ is a permutation matrix, then $q(A)=1$ and if $A$ is diagonal, then $q(A)=det(A)$ (product of the diagonal entries).  Now, suppose $p(X)$ is a homogeneous degree $n$ polynomial in $n^2$ variables (that we think of as the entires of an $n \times n$ matrix $X$).  If $p$ has the following symmetries:

$p(X) = p(X^t)$ (transpose)
$p(AXB) = p(X)$ for all pairs of matrices $(A,B)$ such that $A$ and $B$ are each either permutation matrices or diagonal matrices and $q(A)q(B) = 1$

then $p(X)$ is a constant multiple of $perm(X)$ for all matrices $X$.  Hence we say the permanent is characterized by its symmetries.

More generally, if we have a (homogeneous) polynomial $f(x_1, ..., x_m)$ in $m$ variables, then $GL_m$ (the group of all invertible $m \times m$ matrices) acts on $f$ by $(Af)(x_1,...,x_m) = f(A^{-1}(x_1),...,A^{-1}(x_{m}))$ for $A \in GL_m$ (where we are taking the variables $x_1,...,x_m$ as a basis for the $m$-dimensional vector space on which $GL_m$ naturally acts).  The stabilizer of $f$ in $GL_m$ is the subgroup $\text{Stab}(f) = \{ A \in GL_m : Af = f\}$.  We say $f$ is characterized by its symmetries if the following holds: for any homogeneous polynomial $f'$ in $m$ variables of the same degree as $f$, if $Af' = f'$ for all $A \in \text{Stab}(f)$, then $f'$ is a constant multiple of $f$.


Does every Turing-recognizable undecidable language have a NP-complete subset? Does every Turing-recognizable undecidable language have a NP-complete subset?

The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an infinite decidable subset.

No.

Turing-recognizable undecidable languages can be unary (define $x \not\in L$  unless $x = 0000\ldots 0$, so the only difficult strings are composed solely of 0's). Mahaney's theorem says that no unary language can be NP-complete unless P=NP.


Is there a rule-based implementation of weighted abduction other than the PTTP? Is there an implementation of weighted abduction other than the PT theorem prover? A Google search reveals the PTTP and a few statistical approaches but I'm interested in a rule-based approach. The PTTP is too slow with large knowledge bases. Since I couldn't google up anything useful I guess there's none (maybe statistics is the way to go as abduction is intractable) but maybe someone knows of an alternative in a different branch of logic programming (such as ASP).

I'm not aware of any alternatives but some first-order abductive problems can be recast as evaluation of stable models.


A conjecture on 4-coloring maximal planar graphs The question/task is to prove/disprove the conjecture below.
Let $G$ be a maximal planar graph with a 4-coloring $f$. Let $(a,b,c,d)$ be a cycle in $G$. Let $S$ be the collection of all $a,c$-paths in $G$ and all $b,d$-paths in $G$.
Conjecture: At least two members of $S$ are bicolored.
(i.e., there exist distinct paths $Q_1,Q_2\in S$ and colors $i,j,k,l\in\{1,2,3,4\}$ such that $f(u)\in\{i,j\}$ for every vertex $u$ on $Q_1$ and $f(v)\in\{k,l\}$ for every vertex $v$ on $Q_2$).
Definitions:-
$G$ is a maximal planar graph if it can be drawn on a plane such that no edges cross and boundary of every face is a triangle. A 4-colouring $f$ of $G$ is a function $f:V(G)\to\{1,2,3,4\}$ such that $f$ map endpoints of each edge to different 'colors' (i.e. $f(u)\neq f(v)$ for every edge $uv$ of $G$).
Notes:-
It is easy to see that the conjecture is true if the cycle $(a,b,c.d)$
is tricolored (or bicolored). The following is the crux of the conjecture.
Let $G$ be a planar graph with a 4-coloring $f$. Let $(a,b,c,b)$ be a cycle in $G$ such that boundary of each face inside the cycle is a triangle. Suppose that the cycle $(a,b,c,d)$ receives all four colors.
Conjecture 2: Then, there is a bicolored $a,c$-path or a bicolored $b,d$-path inside the cycle.
If Conjecture 2 is true, then the main conjecture above is true (apply Conjecture 2 to outside region of the cycle $(a,b,c,d)$ ).

Conjecture 2 is already proved.
Quote from J.A. Tilley, The a-graph coloring problem(2017):

Theorem A.1. Let $G$ be an a-graph with boundary cycle $uxvy$ for the exterior 4-face and let $G$ have a 4-coloring $c$. Suppose, without loss of generality, that $c(x)=1$, $c(y)=1$ or 2, $c(u)=3$, and $c(v)=3$ or 4. Then there is either a 1–2 path between $x$ and $y$ or a 3–4 path between $u$ and $v$.

Proof. Suppose that G with 4-coloring c is a minimal counterexample to the theorem. Clearly G cannot have either an interior
xy edge or an interior u v edge. Let X be the set of vertices of G adjacent to x; they form an internal path between u and v that
includes at least one interior vertex of G. At least one of those interior vertices of G belonging to X is colored 2, for otherwise
the path between u and v would be colored 3–4, contradicting the supposition. Contract the various edges joining x to each
vertex of X colored 2, and change the color of x to 2. The result is a 4-colored a-graph F . The edge contractions do not create
any 3–4 path between u and v . By the minimality assumption, F must therefore have a 1–2 path between x and y. Reverse
the contractions and restore the color of x to 1 to reveal a 1–2 path between x and y in G, contradicting the supposition and
establishing the truth of the theorem.

Definiton: in the above paper, an a-graph is a plane graph such that one face has a 4-vertex cycle as boundary and all other faces have a triangle as boundary.


Feasibility of Gödel machines Recently I stumbled upon quite an interesting theoretical construct. A so called  Gödel machine

It's a general problem solver which is capable of self-optimization. It's suitable for reactive environments.

As I understand, it can be implemented as a program for universal Turing machine, although it's requirements go far beyond hardware currently available. I couldn't find many details, though.

Can such machines be built in practice? Are they at least feasible in our Universe?

Can such machines be built in practice?

Yes. By "machine", Schmidhuber just means "computer program".
Are they at least feasible in our Universe?

Not in their current form -- the algorithms are too inefficient.

From a ten thousand meter perspective, Jürgen Schmidhuber (and former students, like Marcus Hutter) have been investigating the idea of combining Levin search with Bayesian reasoning to work out algorithms for general problem-solving.

The basic idea behind Levin search is that it's possible to use dovetailing and Goedel codes to give a single algorithm which is, up to constant factors, optimal. Loosely, you fix a Godel encoding of programs, and then run a Turing machine that runs the $n$-th program once every $2^{n}$ steps. This means that if the $n$-th program is optimal for some problem, then Levin search will "only" be a constant factor of $2^n$ times slower.

They have done a fair amount of work on making the constant factors less stupendously, horrifically awful, and are optimistic that this kind of scheme can work in practice. I am (based on my experience in automated theorem proving) very skeptical, since good data structures are critical to theorem proving, and Goedel encodings are terrible data structures.

But you don't know it can't work until you try to make it work! After all, we already live in a world where people solve problems by reduction to SAT.


Is this variant of bitwise cyclic tag Turing-complete? Cross-posted to MathOverflow.

CT is an extremely minimalist programming language that can simulate arbitrary tag systems, and is therefore Turing-complete. A program consists simply of a string of 3 commands that operate on a queue of bits:

Command
Description

A
pop

B
push 0 if front is 1

C
push 1 if front is 1

These commands are executed in cyclic order from left to right. The queue is initialized with a single 1. If the queue becomes empty, the program terminates.
Let CT2 be the language that replaces command B with "push 0" (unconditionally). Is CT2 Turing-complete? One way to prove this would be to find a way to simulate CT or arbitrary tag systems in it, perhaps through some clever encoding.
Here are the busy beaver sequences for both languages with a 10K-step runtime limit (runtimes exceeding this are considered non-terminating):

Program length
CT
CT2

0
0
0

1
1
1

2
4
1

3
9
3

4
16
8

5
25
19

6
36
17

7
49
49

8
399
899

9
2159
1367

10
1407
300

11
7490
9893

12
9130
3348

Notice that CT2 also exhibits a rapid growth that is suggestive of Turing-completeness.

It is. There's a fairly simple construction compiling from CT to CT2.
First, consider that it's possible to double every command in a CT program without producing any behaviour (that is, A becomes AA, B becomes BB, C becomes CC). The queue of bits now has every bit doubled, but the cycle of commands only does anything with every second bit, so the modified behaviour has the same behaviour as the original.
Let $n$ be the number of A commands in a program. You can observe that pushing a string of $n$ false bits (indeed, any multiple of $n$) will have no effect on a CT program (as will not pushing a string of $n$ false bits), so you can safely write a string of $n$ Bs anywhere in a program without changing its behaviour.
Suppose we take a CT program with every command doubled, and insert a string of $2n$ Bs immediately before each AA pair (i.e. immediately before an A before it was doubled); here, $n$ is the number of A commands after the doubling (i.e. twice the number of A commands in the original program). This does not change the behaviour of the program. Additionally, those Bs that happen to be in even positions can be changed to Cs without changing the behaviour of the program (because the even-numbered bits in the queue are skipped by the second A command of a pair, their values are irrelevant). We can thus change somewhere from $0$ to $n$ of each run of $2n$ inserted Bs into Cs, and produce a CT program which has identical behaviour to the original, and for which additionally the number of Bs between each pair of As is a multiple of $n$.
Now consider what happens if we reinterpret this CT program as a CT2 program. It will have mostly the same behaviour as the CT program, except that sometimes an additional run of a multiple of $n$ false bits will be appended to the queue (due to B commands running when the head of the queue is false). The added bits will always be in runs whose length is a multiple of $n$.
When these runs reach the front of the queue, they will, in effect, end up pushing a number of false bits onto the queue equal to the number of B commands in the entire program (rather than doing nothing, like they would in CT); this happens regardless of where the false bits appear in the queue and regardless of what point of the program we have reached (they cycle through the program from some point in it back to that point again). But this is still going to be a multiple of $n$ (the number of B commands between any two A commands is a multiple of $n$, so the total number of B commands is produced by adding multiples of $n$ and is still a multiple of $n$).
In other words, there's a direct correspondence between CT programs constructed as above (which have the same computational power as CT programs in general), and their reinterpretations as CT2 programs. If you define CT2's halt state as "the queue consists entirely of false bits", this is sufficient to make CT2 Turing-complete. (I don't know whether it's possible for nontrivial CT2 programs to halt if you continue to define the halt condition as the queue being empty, though.)
(As a side note: is this question just a question-in-the-abstract asked out of curiosity, or do you need it as an intermediate result for something? I've been looking at similar but more complex constructions when trying to produce Turing-completeness results for various simple languages, and if you're aiming to do something similar yourself, I'd be interested to know what you're working on.)