User rus9384

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

1

4

votes

2

answers

212

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

1

answer

72

views

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

complexity-theory graphs satisfiability

Dec 8 at 13:04 Community♦ 1

3

votes

0

answers

39

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,309

1

3

votes

1

answer

252

views

Linear time multiplication on RAM machine?

algorithms asymptotics integers multiplication

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

1

3

votes

1

answer

303

views

Satisfiabililty sufficient condition?

satisfiability

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

1

3

votes

2

answers

267

views

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

complexity-theory np

Jun 8 '17 at 23:04 Ariel 11.9k

3

votes

1

answer

114

views

Solving 2-CNF TQBF with #SAT solver?

algorithms reductions

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

1

2

votes

2

answers

2k

views

3-SAT with 3 variable occurences

3-sat

Nov 5 at 8:26 bincob 111

2

votes

1

answer

55

views

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

complexity-theory complexity-classes

Aug 12 at 17:22 Ariel 11.9k

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,125

2

votes

1

answer

135

views

Is boolean formula isomorphism NP-complete?

np-complete boolean-algebra

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

2

votes

1

answer

44

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

2

votes

1

answer

43

views

2CNF with 3 variable occurences

boolean-algebra 2-sat

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

2

votes

1

answer

190

views

Is this case of weighted 2SAT NP-complete?

np-complete 2-sat

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

2

votes

1

answer

113

views

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

satisfiability counting

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

2

votes

1

answer

349

views

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

complexity-theory satisfiability

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

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

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,125

1

vote

0

answers

15

views

Would $\mathsf{P=BPP}$ imply $\mathsf{dIP=IP}$ and if not then why?

complexity-theory np interactive-proof-systems

Nov 17 at 17:06 rus9384 1,309

1

vote

0

answers

17

views

Is undecidability contained in $PSPACE / o(exp(n))$?

complexity-theory undecidability

Nov 7 at 19:10 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

1

vote

2

answers

54

views

What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

complexity-theory time-complexity complexity-classes space-complexity

Aug 8 at 21:55 Dmitry 1,287

1

vote

0

answers

43

views

Are complexity classes equal in this case?

complexity-theory

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

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

39

views

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

satisfiability np

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

1

vote

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,309

1

vote

0

answers

60

views

Determining when equal 2CNF has pure literal

boolean-algebra formal-methods

Sep 4 '17 at 7:20 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 246k

1

vote

0

answers

53

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,309

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

45 Questions

Can minimal CNF contain clause longer than initial CNF?

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

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

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

Linear time multiplication on RAM machine?

Satisfiabililty sufficient condition?

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

Solving 2-CNF TQBF with #SAT solver?

3-SAT with 3 variable occurences

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

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?

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?

Would $\mathsf{P=BPP}$ imply $\mathsf{dIP=IP}$ and if not then why?

Is undecidability contained in $PSPACE / o(exp(n))$?

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

What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

Are complexity classes equal in this case?

Is such variant of SAT always satisfiable?

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

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

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))$?