User rus9384

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

4

votes

2

answers

209

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

65

views

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

complexity-theory graphs satisfiability

Nov 8 at 12:48 rus9384 1,289

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

1

3

votes

1

answer

236

views

Linear time multiplication on RAM machine?

algorithms asymptotics integers multiplication

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

1

3

votes

1

answer

294

views

Satisfiabililty sufficient condition?

satisfiability

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

1

3

votes

2

answers

254

views

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

complexity-theory np

Jun 8 '17 at 23:04 Ariel 11.7k

3

votes

1

answer

99

views

Solving 2-CNF TQBF with #SAT solver?

algorithms reductions

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

2

votes

1

answer

51

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

1

2

votes

2

answers

84

views

Do we know something about this refutation method for SAT?

np-complete satisfiability

Jan 28 at 18:06 Kyle Jones 7,030

2

votes

1

answer

132

views

Is boolean formula isomorphism NP-complete?

np-complete boolean-algebra

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

2

votes

1

answer

43

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

2

votes

1

answer

42

views

2CNF with 3 variable occurences

boolean-algebra 2-sat

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

2

votes

1

answer

175

views

Is this case of weighted 2SAT NP-complete?

np-complete 2-sat

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

2

votes

1

answer

108

views

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

satisfiability counting

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

2

votes

1

answer

320

views

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

complexity-theory satisfiability

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

1

2

votes

1

answer

127

views

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

complexity-theory time-complexity

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

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

1

vote

0

answers

13

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

1

vote

0

answers

13

views

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

complexity-theory undecidability

Nov 7 at 19:10 rus9384 1,289

1

vote

2

answers

2k

views

3-SAT with 3 variable occurences

3-sat

Nov 5 at 8:26 bincob 111

1

vote

0

answers

47

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

1

vote

2

answers

50

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

1

vote

0

answers

43

views

Are complexity classes equal in this case?

complexity-theory

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

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

1

vote

1

answer

38

views

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

satisfiability np

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

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

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

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

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

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?

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

3-SAT with 3 variable occurences

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