Skip to main content
rus9384's user avatar
rus9384's user avatar
rus9384's user avatar
rus9384
  • Member for 7 years, 1 month
  • Last seen this week
2 votes
3 answers
6k 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
834 views

SAT to knapsack vs. ETH

2 votes
1 answer
569 views

Is this case of weighted 2SAT NP-complete?

2 votes
1 answer
535 views

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

3 votes
1 answer
448 views

Linear time multiplication on RAM machine?

0 votes
1 answer
399 views

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

3 votes
1 answer
364 views

Satisfiabililty sufficient condition?

3 votes
2 answers
347 views

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

4 votes
2 answers
269 views

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

1 vote
1 answer
258 views

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

1 vote
1 answer
233 views

How can I understand if reduction is Karp reduction?

0 votes
1 answer
214 views

Colored cliques complexity

3 votes
1 answer
214 views

Is boolean formula isomorphism NP-complete?

3 votes
1 answer
200 views

Solving 2-CNF TQBF with #SAT solver?

2 votes
1 answer
197 views

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

1 vote
0 answers
191 views

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

2 votes
2 answers
173 views

Exponential Time Hypothesis and the input size vs number of variables

0 votes
1 answer
172 views

Another way to solve SAT. Was it known?

2 votes
1 answer
171 views

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

5 votes
0 answers
163 views

Can minimal CNF contain clause longer than initial CNF?

1 vote
0 answers
145 views

Correct implication for 3SAT from this theorem?

2 votes
1 answer
142 views

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

3 votes
1 answer
125 views

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

2 votes
2 answers
117 views

Do we know something about this refutation method for SAT?

1 vote
0 answers
116 views

Is such variant of SAT always satisfiable?

0 votes
1 answer
109 views

Understanding kQBF: changing order of quantification?

1 vote
1 answer
105 views

How 2-QCNF algorithm works?

1 vote
1 answer
101 views

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