New answers tagged cc.complexity-theory
1
As far as Hamiltonian circuit on cubic graphs is natural your conjecture "There is an ASP-reduction between any pair of (natural) NP-complete problems" is false.
There is no ASP-reduction from SAT (another natural problem) to Hamiltonian circuit on cubic graphs, because every cubic graph that has an Hamiltonian cycle has another Hamiltonian cycle different ...
3
@Chandra Chekuri's comment made me think about casting the problem as a maximum flow problem (solvable in polynomial time):
$\forall i$, have a vertex $v_{i}$, connected to the source by an edge with capacity $b_i$.
$\forall i$, $ \forall e \in S_i$, have a vertex $v_{e}$, connected to all $v_j$ such that $e \in S_j$ with capacity $1$, and connected to the ...
4
Create a bipartite graph:
For every element $x\in\bigcup_{i=1}^nS_i$, introduce a corresponding vertex $u(x)$.
For every set $S_i$, introduce a corresponding vertex $v(S_i)$.
Connect vertex $u(x)$ to vertex $v(S_i)$ by an edge, if and only if $x\in S_i$.
Then your problem essentially asks, whether there exists a subset $F$ of the edges, so that
every ...
3
Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a scheme for verifiable quantum computational supremacy based on a strengthening of trap-door claw-free functions (TCFs).
In the above scheme:
Vicky the classical verifier provides a description of a pair of functions $f_0$ and $f_1$ to Peggy the quantum prover, while saving the trapdoor to $f_0$ ...
3
Yes, diagonalization arguments can still be used. For the oracle separation $\mathcal{QMA}^\mathcal{O}\subsetneq \mathcal{PP}^\mathcal{O}$, design an oracle $\mathcal{O}$ such that the following language separates the classes:
$$L = \{1^n\ |\ \left| \mathcal{O}\cap\{0,1\}^n\right|>\tfrac{1}{2}2^n \}$$
This language is clearly in $\mathcal{PP}^\mathcal{O}...
3
The problem you are calling "two-by-two" topological sorting is the Two Processor Scheduling Problem (unit-length jobs, under precedence constraints given by a partial order on the jobs -- i.e., the DAG). The partial order on the jobs constrains them so that if x<y then job y cannot be started until job x is completed. Shelling the vertices of the DAG ...
3
Yes, because you can just concentrate most of the $C$ on a small part of the variables, while for rest of the variables can be contained in a single clause each, with a trivial matching. This way you can raise the relative size of the clauses to any polynomial of the remaining variables.
The question would be more interesting if you required the property ...
6
If you are happy with impying $P=RP$ (which implies $P = ZPP$) but not $P = BPP$, then there is the Stoquastic PCP conjecture (or its classical version, a SetCSP PCP conjecture).
7
I think it is "easy" to come up with an assumption that implies one but not necessarily the other... (just write down a condition that is equivalent to P=ZPP)... however, a "natural" and non-uniform assumption (e.g. some weak form of PRG) seems harder, since (for example) hitting set generators (the non-uniform thing you need for P=RP) imply pseudorandom ...
Top 50 recent answers are included
