User rus9384

1

2

votes

2

answers

3k

views

3-SAT with 3 variable occurences

3-sat

Nov 5 at 8:26 bincob 111

1

vote

2

answers

1k

views

Why AKS primality test is called polynomial?

complexity-theory

May 18 '17 at 15:18 D.W.♦ 130k

1

2

votes

1

answer

1k

views

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

complexity-theory np-complete satisfiability np

Jun 8 '17 at 5:45 Kyle Jones 7,270

1

vote

1

answer

514

views

SAT to knapsack vs. ETH

np-complete satisfiability knapsack-problems

Aug 18 '17 at 15:51 Ariel 12.3k

2

votes

1

answer

365

views

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

complexity-theory satisfiability

Jul 6 '17 at 20:00 rus9384 1,309

1

3

votes

1

answer

305

views

Satisfiabililty sufficient condition?

satisfiability

Aug 21 '17 at 7:57 rus9384 1,309

0

votes

1

answer

282

views

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

algorithms complexity-theory time-complexity decision-problem

May 11 '17 at 20:11 Ariel 12.3k

1

3

votes

1

answer

271

views

Linear time multiplication on RAM machine?

algorithms asymptotics integers multiplication

Sep 13 '17 at 4:24 ryan 4,196

1

3

votes

2

answers

270

views

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

complexity-theory np

Jun 8 '17 at 23:04 Ariel 12.3k

1

4

votes

2

answers

213

views

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

complexity-theory graphs time-complexity runtime-analysis

May 27 '17 at 23:07 Community♦ 1

1

vote

1

answer

200

views

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

np-hard satisfiability boolean-algebra 3-sat

Aug 11 '17 at 17:10 rus9384 1,309

2

votes

1

answer

198

views

Is this case of weighted 2SAT NP-complete?

np-complete 2-sat

Aug 21 '17 at 8:04 Yuval Filmus 249k

0

votes

1

answer

160

views

Colored cliques complexity

complexity-theory graphs clique

May 26 '17 at 15:08 rus9384 1,309

2

votes

1

answer

138

views

Is boolean formula isomorphism NP-complete?

np-complete boolean-algebra

Aug 22 '18 at 8:11 Thinh D. Nguyen 2,195

1

2

votes

1

answer

134

views

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

complexity-theory time-complexity

Jun 27 '17 at 21:23 D.W.♦ 130k

0

votes

1

answer

130

views

Another way to solve SAT. Was it known?

satisfiability sat-solvers

Sep 7 '17 at 14:43 rus9384 1,309

1

vote

0

answers

125

views

Correct implication for 3SAT from this theorem?

complexity-theory np-complete satisfiability

Aug 13 '17 at 15:04 rus9384 1,309

1

vote

0

answers

120

views

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

complexity-theory complexity-classes

Oct 4 at 18:18 rus9384 1,309

3

votes

1

answer

118

views

Solving 2-CNF TQBF with #SAT solver?

algorithms reductions

Jun 2 '17 at 9:46 Yuval Filmus 249k

2

votes

1

answer

114

views

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

satisfiability counting

Aug 13 '17 at 5:09 D.W.♦ 130k

1

vote

1

answer

107

views

How can I understand if reduction is Karp reduction?

reductions

Jun 29 '17 at 14:58 Yuval Filmus 249k

1

4

votes

0

answers

102

views

Can minimal CNF contain clause longer than initial CNF?

boolean-algebra normal-forms

Mar 18 '20 at 11:05 xxx 1

0

votes

0

answers

89

views

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

complexity-theory

Sep 16 '17 at 2:28 rus9384 1,309

1

2

votes

2

answers

87

views

Do we know something about this refutation method for SAT?

np-complete satisfiability

Jan 28 '20 at 18:06 Kyle Jones 7,270

1

vote

0

answers

85

views

Is such variant of SAT always satisfiable?

boolean-algebra 3-sat

Sep 10 '17 at 22:51 rus9384 1,309

1

vote

1

answer

81

views

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

algorithms logic satisfiability

Aug 31 '17 at 9:51 Yuval Filmus 249k

3

votes

1

answer

72

views

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

complexity-theory graphs satisfiability

Dec 8 at 13:04 Community♦ 1

0

votes

1

answer

70

views

Understanding kQBF: changing order of quantification?

np-hard boolean-algebra propositional-logic

Aug 25 '17 at 13:08 rus9384 1,309

1

vote

0

answers

66

views

Question about $\mathsf{Almost–PSPACE}$

complexity-theory oracle-machines

Jun 5 '17 at 12:15 David Richerby 78.8k

1

vote

1

answer

65

views

Correctness of following algorithm for 3-QCNF?

algorithms satisfiability

Jun 21 '17 at 18:18 Kyle Jones 7,270

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

45 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?

Satisfiabililty sufficient condition?

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

Linear time multiplication on RAM machine?

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?

Is this case of weighted 2SAT NP-complete?

Colored cliques complexity

Is boolean formula isomorphism NP-complete?

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

Another way to solve SAT. Was it known?

Correct implication for 3SAT from this theorem?

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

Solving 2-CNF TQBF with #SAT solver?

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

How can I understand if reduction is Karp reduction?

Can minimal CNF contain clause longer than initial CNF?

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

Do we know something about this refutation method for SAT?

Is such variant of SAT always satisfiable?

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

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

Understanding kQBF: changing order of quantification?

Question about $\mathsf{Almost–PSPACE}$

Correctness of following algorithm for 3-QCNF?