User rus9384

3

votes

1

answer

72

views

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

Dec 8 at 13:04 Community♦ 1

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

18

views

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

complexity-theory undecidability

Nov 7 at 19:10 rus9384 1,309

1

2

votes

2

answers

3k

views

3-SAT with 3 variable occurences

3-sat

Nov 5 at 8:26 bincob 111

0

votes

0

answers

36

views

Are all reductions from NP-complete problems either NP-complete or are contained in P?

complexity-theory reductions np

Oct 25 at 18:48 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

2

votes

1

answer

58

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

1

vote

2

answers

55

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

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

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

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

vote

0

answers

43

views

Are complexity classes equal in this case?

complexity-theory

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

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

2

votes

1

answer

45

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

0

votes

0

answers

89

views

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

complexity-theory

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

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

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

40

views

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

satisfiability np

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

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

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

61

views

Determining when equal 2CNF has pure literal

boolean-algebra formal-methods

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

2

votes

1

answer

44

views

2CNF with 3 variable occurences

boolean-algebra 2-sat

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

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

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

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

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

1

3

votes

1

answer

305

views

Satisfiabililty sufficient condition?

satisfiability

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

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

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

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

45 Questions

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

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

Are all reductions from NP-complete problems either NP-complete or are contained in P?

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

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

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

Can minimal CNF contain clause longer than initial CNF?

Do we know something about this refutation method for SAT?

Is boolean formula isomorphism NP-complete?

Are complexity classes equal in this case?

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

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

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

Linear time multiplication on RAM machine?

Is such variant of SAT always satisfiable?

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

Another way to solve SAT. Was it known?

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

Determining when equal 2CNF has pure literal

2CNF with 3 variable occurences

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

Understanding kQBF: changing order of quantification?

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

Is this case of weighted 2SAT NP-complete?

Satisfiabililty sufficient condition?

SAT to knapsack vs. ETH

Correct implication for 3SAT from this theorem?

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