User rus9384

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

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

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

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

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

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

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

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

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

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

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

vote

1

answer

39

views

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

satisfiability np

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

0

votes

1

answer

124

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

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

43

views

2CNF with 3 variable occurences

boolean-algebra 2-sat

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

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

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

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

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

189

views

Is this case of weighted 2SAT NP-complete?

np-complete 2-sat

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

1

vote

1

answer

505

views

SAT to knapsack vs. ETH

np-complete satisfiability knapsack-problems

Aug 18 '17 at 15:51 Ariel 11.9k

1

vote

0

answers

122

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

113

views

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

satisfiability counting

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

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

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

1

vote

1

answer

64

views

How 2-QCNF algorithm works?

graphs satisfiability 2-sat

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

45 Questions

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

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

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}$

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?

Do we know something about this refutation method for SAT?

Is such variant of SAT always satisfiable?

Linear time multiplication on RAM machine?

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?

3-SAT with 3 variable occurences

2CNF with 3 variable occurences

Determining when equal 2CNF has pure literal

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

Is boolean formula isomorphism NP-complete?

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?

SAT to knapsack vs. ETH

Correct implication for 3SAT from this theorem?

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

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

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

How 2-QCNF algorithm works?