User rus9384

2 votes

3 answers

5k views

3-SAT with 3 variable occurences

asked Sep 5, 2017 at 8:22

1 vote

2 answers

2k views

Why AKS primality test is called polynomial?

asked May 18, 2017 at 14:08

2 votes

1 answer

2k views

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

asked May 19, 2017 at 15:29

1 vote

1 answer

767 views

SAT to knapsack vs. ETH

asked Aug 18, 2017 at 14:55

2 votes

1 answer

521 views

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

asked Jun 13, 2017 at 2:23

2 votes

1 answer

515 views

Is this case of weighted 2SAT NP-complete?

asked Aug 19, 2017 at 16:08

3 votes

1 answer

425 views

Linear time multiplication on RAM machine?

asked Sep 9, 2017 at 0:27

0 votes

1 answer

381 views

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

asked May 11, 2017 at 10:28

3 votes

1 answer

356 views

Satisfiabililty sufficient condition?

asked Jul 11, 2017 at 23:54

3 votes

2 answers

340 views

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

asked Jun 8, 2017 at 10:07

4 votes

2 answers

256 views

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

asked May 27, 2017 at 9:36

1 vote

1 answer

255 views

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

asked Aug 11, 2017 at 14:49

0 votes

1 answer

208 views

Colored cliques complexity

asked May 26, 2017 at 10:26

1 vote

1 answer

204 views

How can I understand if reduction is Karp reduction?

asked Jun 29, 2017 at 10:07

3 votes

1 answer

200 views

Is boolean formula isomorphism NP-complete?

asked Aug 28, 2017 at 1:49

3 votes

1 answer

189 views

Solving 2-CNF TQBF with #SAT solver?

asked Jun 2, 2017 at 9:15

1 vote

0 answers

179 views

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

asked Oct 4, 2020 at 18:18

2 votes

1 answer

178 views

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

asked Aug 12, 2017 at 11:23

0 votes

1 answer

167 views

Another way to solve SAT. Was it known?

asked Sep 7, 2017 at 9:16

2 votes

1 answer

162 views

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

asked Jun 24, 2017 at 13:54

2 votes

2 answers

155 views

Exponential Time Hypothesis and the input size vs number of variables

asked May 13, 2022 at 12:44

1 vote

0 answers

142 views

Correct implication for 3SAT from this theorem?

asked Aug 13, 2017 at 12:09

2 votes

1 answer

123 views

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

asked Aug 12, 2020 at 14:43

4 votes

0 answers

122 views

Can minimal CNF contain clause longer than initial CNF?

asked Jun 17, 2017 at 12:57

3 votes

1 answer

118 views

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

asked Aug 9, 2017 at 13:15

2 votes

2 answers

113 views

Do we know something about this refutation method for SAT?

asked Sep 13, 2017 at 22:33

1 vote

0 answers

111 views

Is such variant of SAT always satisfiable?

asked Sep 10, 2017 at 22:11

1 vote

1 answer

104 views

How 2-QCNF algorithm works?

asked Aug 7, 2017 at 11:25

1 vote

1 answer

98 views

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

asked Aug 31, 2017 at 0:55

0 votes

0 answers

96 views

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

asked Sep 15, 2017 at 20:06

Stack Exchange Network

54 Questions

3-SAT with 3 variable occurences

Why AKS primality test is called polynomial?

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

SAT to knapsack vs. ETH

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

Is this case of weighted 2SAT NP-complete?

Linear time multiplication on RAM machine?

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

Satisfiabililty sufficient condition?

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

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

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

Colored cliques complexity

How can I understand if reduction is Karp reduction?

Is boolean formula isomorphism NP-complete?

Solving 2-CNF TQBF with #SAT solver?

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

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

Another way to solve SAT. Was it known?

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

Exponential Time Hypothesis and the input size vs number of variables

Correct implication for 3SAT from this theorem?

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

Can minimal CNF contain clause longer than initial CNF?

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

Do we know something about this refutation method for SAT?

Is such variant of SAT always satisfiable?

How 2-QCNF algorithm works?

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

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