New answers tagged cc.complexity-theory
5
I think there is at least one model of computation where 2-SAT is easy and Clique is provably hard: resolution refutation complexity (i.e. how hard is to deduce contradiction from the initial clauses using resolution inference rule). If you think about decision problem instead of refutation, you may ask "how hard is for a Resolution based SAT-solver to ...
8
2-SAT is NL-complete so separating 2-SAT from Clique would separate NP from NL, also a major open problem.
7
This is a search problem rather than a decision problem: factorization of polynomials over finite fields can be done in randomized polynomial time (TFZPP) using the Cantor–Zassenhaus algorithm, but no deterministic (FP) algorithm is known (this is open even for the special case of computing square roots modulo primes).
You can turn it into a (less natural) ...
8
Here is a natural problem known to be in $\mathsf{BPP}$ but not $\mathsf{RP} \cup \mathsf{coRP}$, Problem 2.6 of [1]: Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \times d$ matrices over $\mathbb{F}_{p}$, does the group generated by $A$ have a quotient of order $\geq N$ with no abelian normal subgroups? In [1] it is shown that ...
Top 50 recent answers are included