User rus9384

1 vote

1 answer

768 views

SAT to knapsack vs. ETH

asked Aug 18, 2017 at 14:55

1 vote

1 answer

49 views

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

asked Sep 8, 2017 at 10:41

1 vote

1 answer

98 views

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

asked Aug 31, 2017 at 0:55

1 vote

0 answers

66 views

Determining when equal 2CNF has pure literal

asked Aug 31, 2017 at 21:52

1 vote

0 answers

111 views

Is such variant of SAT always satisfiable?

asked Sep 10, 2017 at 22:11

1 vote

1 answer

59 views

Semi-bounded probabilistic polynomial-time, is it equal to BPP?

asked Jul 23, 2022 at 10:30

1 vote

0 answers

29 views

Complexity class of a problem asking for a chance of receiving an item

asked Nov 24 at 12:28

1 vote

1 answer

20 views

How is $\mathsf{RP\cap UP}$ not a class containing only unsatisfying languages?

asked Dec 2 at 12:35

1 vote

0 answers

179 views

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

asked Oct 4, 2020 at 18:18

1 vote

0 answers

45 views

Are complexity classes equal in this case?

asked Mar 31, 2018 at 23:22

1 vote

2 answers

75 views

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

asked Aug 8, 2020 at 19:42

1 vote

0 answers

27 views

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

asked Nov 7, 2020 at 19:10

0 votes

1 answer

53 views

Universal quantification and the number of solutions

asked May 10, 2022 at 23:43

0 votes

0 answers

39 views

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

asked Oct 25, 2020 at 15:10

0 votes

1 answer

27 views

What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?

asked Nov 27 at 18:00

0 votes

1 answer

54 views

Is it an open problem if CDCL algorithms violate SETH?

asked Jul 8 at 23:13

0 votes

1 answer

26 views

A machine with multiple oracles

asked Oct 12 at 18:57

0 votes

0 answers

96 views

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

asked Sep 15, 2017 at 20:06

0 votes

1 answer

94 views

Understanding kQBF: changing order of quantification?

asked Aug 24, 2017 at 23:08

0 votes

1 answer

167 views

Another way to solve SAT. Was it known?

asked Sep 7, 2017 at 9:16

0 votes

1 answer

61 views

Is following SAT case in $\mathsf{P}$?

asked Jun 8, 2017 at 21:47

0 votes

1 answer

381 views

Are poly-reductions to PSPACE problems for following problems are known?

asked May 11, 2017 at 10:28

0 votes

1 answer

208 views

Colored cliques complexity

asked May 26, 2017 at 10:26

-1 votes

1 answer

36 views

Schaefer's dichotomy theorem and limits on the formula length

asked Jul 7 at 14:06

Stack Exchange Network

54 Questions

SAT to knapsack vs. ETH

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

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

Determining when equal 2CNF has pure literal

Is such variant of SAT always satisfiable?

Semi-bounded probabilistic polynomial-time, is it equal to BPP?

Complexity class of a problem asking for a chance of receiving an item

How is $\mathsf{RP\cap UP}$ not a class containing only unsatisfying languages?

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

Are complexity classes equal in this case?

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

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

Universal quantification and the number of solutions

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

What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?

Is it an open problem if CDCL algorithms violate SETH?

A machine with multiple oracles

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

Understanding kQBF: changing order of quantification?

Another way to solve SAT. Was it known?

Is following SAT case in $\mathsf{P}$?

Are poly-reductions to PSPACE problems for following problems are known?

Colored cliques complexity

Schaefer's dichotomy theorem and limits on the formula length