1
$\begingroup$

I'm exploring an algorithm that solves k-SAT. It uses a ton of preprocessing, so I'm thinking that this will be a circuit bounds.

Without knowing the runtime, I speculate on how quickly it will solve k-SAT instances. It will either solve all instances of k-SAT with probability $p$, or it won't be able to solve any instances. The runtime is based on $p$. Essentially, it runs in quasi-polynomial time.

So essentially, what we have is an algorithm that runs in time $2^{O((\log{n})^{c_1})}\cdot O(c_2 + q)$, and solves all instances with probability $\frac{2^q-1}{2^q}$, or it can't solve any instances. Here, $c_1$ and $c_2$ are constants.

It also requires space polynomial in $q$.

I'm trying to find what complexity class this is, and what is known about it.

SOME NOTES

Just to ensure I've described this correctly, I have an algorithm that either solves all instances, or it can't solve any. We can say it uses $2^{2^n}$ preprocessing. Then, it runs in time that is quasi-polynomial multiplied by a function of $q$.

THE QUESTION, AGAIN

What complexity class is this, and what is known about it?

Improve this question
$\endgroup$
  • $\begingroup$ Your terminology is a bit off. You write, "which complexity class is this?", but you don't seem to be defining one. You talk about algorithms, but problems go into complexity classes. Also, what exactly is your random experiment? Picking an algorithm (from which class?) at random? $\endgroup$ – Raphael♦ Nov 20 '14 at 19:01
  • $\begingroup$ @Raphael: Sorry, I'll try to explain. I'm really talking about a k-SAT algorithm, and I'm trying to find how to describe it in terms of things like complexity classes, but I guess I need a different way to describe it. The algorithm uses a data structure to help it solve the k-SAT problem, which it can either solve all instances for a particular $n$ variables, $m$ clauses, and $k$, or none at all. It can solve everything with probability $p^\alpha, p>1/2$, and the time and space requirements grow linearly with $\alpha$. I was trying to find if this is a new result, which it seems to be. $\endgroup$ – Matt Groff Nov 20 '14 at 19:15
  • $\begingroup$ @Raphael: The random experiment is picking some additional values at random, to add to the data structure, which helps it to solve all problems (in the k-SAT problem class with a given $n$ and $m$) with increased probability. $\endgroup$ – Matt Groff Nov 20 '14 at 19:33
  • $\begingroup$ Increasing $\alpha$ makes that result increasingly useless. $\:$ What's more interesting is how $\hspace{1.24 in}$ the resource requirements grow as $\alpha$ goes to zero. $\:$ If that growth rate is slow enough, $\hspace{1.06 in}$ then your algorithm may place k-SAT in QP/quasipoly. $\;\;\;\;$ $\endgroup$ – user12859 Nov 21 '14 at 1:54
  • $\begingroup$ @RickyDemer: Sorry, I wrote those comments in haste - it should be with probability $(1-p)^\alpha, p<1/2$. What I'm trying to convey is that, from what I understand, with high probability, we can find a circuit that solves all instances of k-SAT with given $m$ and $n$ in pseudopolynomial time and space. Wouldn't these circuits be significant results? $\endgroup$ – Matt Groff Nov 21 '14 at 2:04
1
$\begingroup$

Assuming that the probability is over the randomized preprocessing and $p > 0$, by fixing the correct random choice you get a circuit of size $S = O(2^{\log^{O(1)} n} q^{O(1)})$ for $k$-SAT. The corresponding complexity class is non-uniform circuits of size $S$. If, for example, $q$ is quasipolynomial ($2^{\log^{O(1)}n}$), the you get a non-uniform circuit of quasipolynomial size.

We usually don't care too much about the time required to construct the circuit unless it is very low.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks, Dr. Filmus. Maybe you can answer another question related to this. See the comments to Dr. Ryan William's answer to my question here: cstheory.stackexchange.com/questions/9654/… I'm really just trying to find if I have a useful circuit algorithm... $\endgroup$ – Matt Groff Nov 20 '14 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.