User rus9384

1

2

votes

2

answers

2k

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.♦ 127k

1

2

votes

1

answer

1k

views

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

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

1

vote

1

answer

503

views

SAT to knapsack vs. ETH

np-complete satisfiability knapsack-problems

Aug 18 '17 at 15:51 Ariel 11.9k

2

votes

1

answer

341

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

300

views

Satisfiabililty sufficient condition?

satisfiability

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

0

votes

1

answer

271

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 11.9k

1

3

votes

2

answers

263

views

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

complexity-theory np

Jun 8 '17 at 23:04 Ariel 11.9k

1

3

votes

1

answer

238

views

Linear time multiplication on RAM machine?

algorithms asymptotics integers multiplication

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

1

4

votes

2

answers

210

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

198

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

182

views

Is this case of weighted 2SAT NP-complete?

np-complete 2-sat

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

0

votes

1

answer

158

views

Colored cliques complexity

complexity-theory graphs clique

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

2

votes

1

answer

134

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

130

views

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

complexity-theory time-complexity

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

0

votes

1

answer

123

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

121

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

116

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

112

views

Solving 2-CNF TQBF with #SAT solver?

algorithms reductions

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

2

votes

1

answer

110

views

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

satisfiability counting

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

1

4

votes

0

answers

101

views

Can minimal CNF contain clause longer than initial CNF?

boolean-algebra normal-forms

Mar 18 at 11:05 xxx 1

1

vote

1

answer

98

views

How can I understand if reduction is Karp reduction?

reductions

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

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

86

views

Do we know something about this refutation method for SAT?

np-complete satisfiability

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

1

vote

0

answers

84

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 241k

3

votes

1

answer

71

views

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

complexity-theory graphs satisfiability

Dec 8 at 13:04 Community♦ 1

0

votes

1

answer

69

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.5k

1

vote

1

answer

64

views

Correctness of following algorithm for 3-QCNF?

algorithms satisfiability

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

Stack Exchange Network

current community

your communities

more stack exchange communities

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?

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

Linear time multiplication on RAM machine?

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

Can minimal CNF contain clause longer than initial CNF?

How can I understand if reduction is Karp reduction?

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?