User rus9384

1

4

votes

0

answers

100

views

Can minimal CNF contain clause longer than initial CNF?

boolean-algebra normal-forms

Mar 18 at 11:05 xxx 1

1

4

votes

2

answers

206

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

3

votes

0

answers

38

views

How hard is it to find the length of multiplicative 2-partition?

complexity-theory number-theory

Feb 14 '18 at 20:10 rus9384 1,233

1

3

votes

1

answer

221

views

Linear time multiplication on RAM machine?

algorithms asymptotics integers multiplication

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

1

3

votes

1

answer

294

views

Satisfiabililty sufficient condition?

satisfiability

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

3

votes

0

answers

56

views

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

complexity-theory graphs satisfiability

Aug 9 '17 at 19:07 rus9384 1,233

1

3

votes

2

answers

239

views

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

complexity-theory np

Jun 8 '17 at 23:04 Ariel 11.5k

3

votes

1

answer

94

views

Solving 2-CNF TQBF with #SAT solver?

algorithms reductions

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

1

2

votes

2

answers

81

views

Do we know something about this refutation method for SAT?

np-complete satisfiability

Jan 28 at 18:06 Kyle Jones 6,875

2

votes

1

answer

126

views

Is boolean formula isomorphism NP-complete?

np-complete boolean-algebra

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

2

votes

1

answer

42

views

Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?

search-algorithms

Dec 7 '17 at 7:06 D.W.♦ 122k

2

votes

1

answer

58

views

If we allow a database, what complexity class it is?

complexity-theory databases oracle-machines

Sep 6 '17 at 7:57 rus9384 1,233

2

votes

1

answer

39

views

2CNF with 3 variable occurences

boolean-algebra 2-sat

Sep 1 '17 at 8:29 Yuval Filmus 229k

2

votes

1

answer

162

views

Is this case of weighted 2SAT NP-complete?

np-complete 2-sat

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

2

votes

1

answer

103

views

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

satisfiability counting

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

2

votes

1

answer

294

views

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

complexity-theory satisfiability

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

1

2

votes

1

answer

126

views

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

complexity-theory time-complexity

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

1

2

votes

1

answer

995

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 6,875

1

vote

0

answers

42

views

Are complexity classes equal in this case?

complexity-theory

Apr 1 '18 at 2:54 rus9384 1,233

1

vote

0

answers

83

views

Is such variant of SAT always satisfiable?

boolean-algebra 3-sat

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

1

vote

1

answer

37

views

Paired resolution and $\mathsf{NP}$ vs. $\mathsf{coNP}$?

satisfiability np

Sep 8 '17 at 11:58 Yuval Filmus 229k

1

vote

1

answer

2k

views

3-SAT with 3 variable occurences

3-sat

Sep 5 '17 at 18:27 David Richerby 77.8k

1

vote

0

answers

58

views

Determining when equal 2CNF has pure literal

boolean-algebra formal-methods

Sep 4 '17 at 7:20 rus9384 1,233

1

vote

1

answer

79

views

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

algorithms logic satisfiability

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

1

vote

0

answers

52

views

Is it suspected that $DTIME(o(f(n)))\subsetneq DTIME(f(n))$?

complexity-theory time-complexity complexity-classes

Aug 24 '17 at 10:32 rus9384 1,233

1

vote

1

answer

476

views

SAT to knapsack vs. ETH

np-complete satisfiability knapsack-problems

Aug 18 '17 at 15:51 Ariel 11.5k

1

vote

0

answers

113

views

Correct implication for 3SAT from this theorem?

complexity-theory np-complete satisfiability

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

1

vote

1

answer

165

views

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

np-hard satisfiability boolean-algebra 3-sat

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

1

vote

1

answer

57

views

How 2-QCNF algorithm works?

graphs satisfiability 2-sat

Aug 7 '17 at 12:58 Yuval Filmus 229k

1

vote

1

answer

92

views

How can I understand if reduction is Karp reduction?

reductions

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

39 Questions

Can minimal CNF contain clause longer than initial CNF?

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

How hard is it to find the length of multiplicative 2-partition?

Linear time multiplication on RAM machine?

Satisfiabililty sufficient condition?

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

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

Solving 2-CNF TQBF with #SAT solver?

Do we know something about this refutation method for SAT?

Is boolean formula isomorphism NP-complete?

Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?

If we allow a database, what complexity class it is?

2CNF with 3 variable occurences

Is this case of weighted 2SAT NP-complete?

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

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

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

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

Are complexity classes equal in this case?

Is such variant of SAT always satisfiable?

Paired resolution and $\mathsf{NP}$ vs. $\mathsf{coNP}$?

3-SAT with 3 variable occurences

Determining when equal 2CNF has pure literal

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

Is it suspected that $DTIME(o(f(n)))\subsetneq DTIME(f(n))$?

SAT to knapsack vs. ETH

Correct implication for 3SAT from this theorem?

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

How 2-QCNF algorithm works?

How can I understand if reduction is Karp reduction?