# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

3,090 questions
Filter by
Sorted by
Tagged with
1 vote
32 views

### Clause Density for guaranteed Easy (2, 3) SAT Cases

It is known that its NP-Complete to decide the satisfiability of 3-SAT instances in which every variable occurs four times. Now given a (2, 3)-SAT instance where each clause has length 2 or 3. ...
• 821
77 views

### Solving #SAT through TQBF

I'm not extremely proficient with counting complexity classes, but since #SAT is #P-complete, its decision version, let's call it #SAT(D) (is the number of solutions less than some $k$), is in PSPACE. ...
• 1,670
127 views

### Complexity of 2-coloring with extra constraints

I am considering the following problem: Given a graph $G=(V,E)$ with $|V|=4n$ vertices, can we color the vertices in two colors (red and blue) with The usual constraint that two vertices connected by ...
• 121
59 views

### EXPSPACE-complete optimization problems

This is similar to this question but specifically for optimization problems. Which are some optimization problems that (have corresponding decision problems that) are EXPSPACE-complete?
• 1,670
1 vote
143 views

### Use of transitive closure in proof of NC hierarchy collapse

Im looking at the proof of $NC^{i} = NC^{i+1} \implies NC = NC^i,\,i\geq 1$ in page 10 of the following article: https://www.cs.uoregon.edu/Reports/TR-1986-001.pdf I understand the general idea ...
• 11
48 views

• 11.5k
161 views

### Searching for a proof that non-deterministic logspace with errors is contained in $PL$

In this 10 year old question Non-deterministic logspace with two-sided error the author asked for a complexity class related to $NL$. Namely $NL$ but we are allowed to have two-sided error for the ...
• 21
80 views

### Reference request: finite field computation over the Word-RAM model

Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$. Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and ...
• 686