User rus9384

2

votes

1

answer

46

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

1

vote

2

answers

45

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

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

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

2

votes

1

answer

131

views

Is boolean formula isomorphism NP-complete?

np-complete boolean-algebra

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

1

vote

0

answers

43

views

Are complexity classes equal in this case?

complexity-theory

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

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

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

0

votes

0

answers

85

views

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

complexity-theory

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

1

3

votes

1

answer

225

views

Linear time multiplication on RAM machine?

algorithms asymptotics integers multiplication

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

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

1

vote

1

answer

37

views

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

satisfiability np

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

0

votes

1

answer

121

views

Another way to solve SAT. Was it known?

satisfiability sat-solvers

Sep 7 '17 at 14:43 rus9384 1,267

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

1

vote

1

answer

2k

views

3-SAT with 3 variable occurences

3-sat

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

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

2

votes

1

answer

39

views

2CNF with 3 variable occurences

boolean-algebra 2-sat

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

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

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

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

2

votes

1

answer

163

views

Is this case of weighted 2SAT NP-complete?

np-complete 2-sat

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

1

3

votes

1

answer

294

views

Satisfiabililty sufficient condition?

satisfiability

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

1

vote

1

answer

477

views

SAT to knapsack vs. ETH

np-complete satisfiability knapsack-problems

Aug 18 '17 at 15:51 Ariel 11.6k

1

vote

0

answers

115

views

Correct implication for 3SAT from this theorem?

complexity-theory np-complete satisfiability

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

2

votes

1

answer

105

views

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

satisfiability counting

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

1

vote

1

answer

180

views

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

np-hard satisfiability boolean-algebra 3-sat

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

3

votes

0

answers

57

views

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

complexity-theory graphs satisfiability

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

1

vote

1

answer

57

views

How 2-QCNF algorithm works?

graphs satisfiability 2-sat

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

2

votes

1

answer

300

views

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

complexity-theory satisfiability

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

1

vote

1

answer

92

views

How can I understand if reduction is Karp reduction?

reductions

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

41 Questions

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?

3-SAT with 3 variable occurences

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

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

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

How 2-QCNF algorithm works?

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

How can I understand if reduction is Karp reduction?