rus9384's user avatar
rus9384's user avatar
rus9384's user avatar
rus9384
  • Member for 6 years, 7 months
  • Last seen this week
2 votes
3 answers
5k views

3-SAT with 3 variable occurences

1 vote
2 answers
2k views

Why AKS primality test is called polynomial?

2 votes
1 answer
2k views

$NP \ vs \ co-NP$: tautology to SAT and vice versa?

1 vote
1 answer
767 views

SAT to knapsack vs. ETH

2 votes
1 answer
521 views

Reduction from 2-SAT to 2-XOR-SAT?

2 votes
1 answer
515 views

Is this case of weighted 2SAT NP-complete?

3 votes
1 answer
425 views

Linear time multiplication on RAM machine?

0 votes
1 answer
381 views

Are poly-reductions to PSPACE problems for following problems are known?

3 votes
1 answer
356 views

Satisfiabililty sufficient condition?

3 votes
2 answers
340 views

Is it possible to prove $\mathsf{BPP = NP}$ statistically?

4 votes
2 answers
256 views

Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?

1 vote
1 answer
255 views

Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

0 votes
1 answer
208 views

Colored cliques complexity

1 vote
1 answer
204 views

How can I understand if reduction is Karp reduction?

3 votes
1 answer
200 views

Is boolean formula isomorphism NP-complete?

3 votes
1 answer
189 views

Solving 2-CNF TQBF with #SAT solver?

1 vote
0 answers
179 views

What is the smallest time/space complexity class for which no sparse language is hard?

2 votes
1 answer
178 views

Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT

0 votes
1 answer
167 views

Another way to solve SAT. Was it known?

2 votes
1 answer
162 views

Was it known that $\mathsf{LTIME \subsetneq NLTIME}$?

2 votes
2 answers
155 views

Exponential Time Hypothesis and the input size vs number of variables

1 vote
0 answers
142 views

Correct implication for 3SAT from this theorem?

2 votes
1 answer
123 views

Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem?

4 votes
0 answers
122 views

Can minimal CNF contain clause longer than initial CNF?

3 votes
1 answer
118 views

What is complexity class for #XOR-2-SAT?

2 votes
2 answers
113 views

Do we know something about this refutation method for SAT?

1 vote
0 answers
111 views

Is such variant of SAT always satisfiable?

1 vote
1 answer
104 views

How 2-QCNF algorithm works?

1 vote
1 answer
98 views

Is it an open problem if generalized resolution is always possible?

0 votes
0 answers
96 views

Is this problem $\mathsf{NEXP}$-complete?