6
As complexity classes LIN, QUAD, CUB etc are not well-behaved, and not easy to handle.
In the definition, you must freeze the model of computation (that is, deterministic Turing machines with one tape). So you will do complexity theory in a single artificial model.
The definition of these classes is fragile: In contrast to our standard complexity classes, ...
6
Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They use spatial locality to put the states of local systems into primary memory, and record the whole state in secondary memory. If you can't contain the whole state ...
5
Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI.
The problem for partial orders is also GI-complete: We can reduce bipartite graph isomorphism (which is GI-complete) to 2 instances of DAG isomorphism where the DAG equals its transitive closure by considering two canonical ways to turn a ...
5
I'm not sure how to answer (1), but (2) is known to imply circuit lower bounds against NQP (non-deterministic quasi-polynomial time). This is from Cody Murray and Ryan Williams' STOC 2018 paper.
In fact, they show that these lower bounds follow from faster algorithms for what they call Gap Circuit Unsatisfiability: given a circuit $C$ on $n$ variables and ...
5
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:...
5
For each of these proof systems we know that there are some formulas where the shortest proof needs to have exponential length. Some of the earliest examples are an exponential lower bound for the pigeonhole principle in polynomial calculus (Razborov '98, IPS '99), and an exponential lower bound for the clique-colouring formula in cutting planes (Pudlák '99)....
5
If I got this right, $\Pi_2L$ as defined above is equal to co-NP. The co-NP-complete DNF tautology sits in $\Pi_2L$: Use z for the assignment and y to choose which clause to check. To show $\Pi_2L$ in co-NP, universally guess z and the rest can be computed in P.
4
With an idea by Louis Jachiet, we managed to design a PTIME algorithm for this task. Long story short, it's a dynamic programming algorithm where you sort the $b$'s by decreasing "ending time" (i.e., by increasing $q_i$ above), consider the $b$'s by intervals of "starting time" (the $p_i$ above), and restrict the search to greedy schedulings that follow the ...
4
Solving Parity games has recently been shown to be in QP:
https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf
Parity games arise naturally in many formal verification contexts, such as LTL synthesis and $\mu$-calculus satisfiabiability.
Parity games were known to be in $NP\cap coNP$, and even in $UP\cap coUP$. In addition, there have been repeated ...
2
In Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems by Aram Harrow, Saeed Mehraban, and Mehdi Soleimanifar
a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point
is presented.
Not ...
2
The scaled down version of $\mathsf{PH}$ versus $\mathsf{PP}$ is $\mathsf{AC}^0$ versus $MAJ \circ \mathsf{AC}^0$, and we know that for the latter there is an exponential separation. Of course, this separation doesn't propagate exponentially up, but you could take this as philosophical evidence that $\mathsf{PH}$ is different enough from $\mathsf{PP}$ that ...
2
We'll argue that the following formulation of OP's problem is complete for OPT#P under poly-time reductions:
input: A Boolean formula $\phi\big(b=(b_1,b_2,\ldots,b_n), x=(x_1, x_2,\ldots, x_m)\big)$
output: The maximum, over all assignments to $b$, of the number of assignments to $x$ such that $\phi(b, x)$ is satisfied (evaluates to true).
The problem ...
1
The class $AWPP$ is not known to be closed under union, though it is easy to show it is closed under intersection
For the class $A_0PP$ it's the other way around: it is closed under intersection, but not known to be closed under union.
These classes have nice machine model definitions, namely they are something akin to an abstract version of the quantum ...
1
Don't forget that even though the fan-in is unbounded, the number of gates is polynomially bounded in the number of variables $n$ (in the definition of $\mathsf{AC}$ for instance) .
1
It is perhaps reasonable to think that circuits that people would come up with would come along with easily verifiable proofs of their correctness. (This was indirectly inspired by Dietrich & Wilson's notion of "groups of black box type", and is in the spirit of Hartmanis's "provable complexity.") Towards this end, we consider:
Definition: "Certified $...
Only top voted, non community-wiki answers of a minimum length are eligible
