User rus9384

1 vote

1 answer

19 views

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

asked Dec 2 at 12:35

0 votes

1 answer

26 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

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

0 votes

1 answer

26 views

A machine with multiple oracles

asked Oct 12 at 18:57

0 votes

1 answer

54 views

Is it an open problem if CDCL algorithms violate SETH?

asked Jul 8 at 23:13

-1 votes

1 answer

36 views

Schaefer's dichotomy theorem and limits on the formula length

asked Jul 7 at 14:06

1 vote

1 answer

59 views

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

asked Jul 23, 2022 at 10:30

2 votes

2 answers

155 views

Exponential Time Hypothesis and the input size vs number of variables

asked May 13, 2022 at 12:44

0 votes

1 answer

53 views

Universal quantification and the number of solutions

asked May 10, 2022 at 23:43

3 votes

0 answers

56 views

Assuming $\mathsf{P=BPP}$ would it be possible to derandomize the verifier in Interactive Proof systems?

asked Nov 17, 2020 at 17:06

1 vote

0 answers

27 views

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

asked Nov 7, 2020 at 19:10

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

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

2 votes

1 answer

123 views

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

asked Aug 12, 2020 at 14:43

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

45 views

Are complexity classes equal in this case?

asked Mar 31, 2018 at 23:22

3 votes

0 answers

44 views

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

asked Feb 14, 2018 at 7:39

2 votes

1 answer

63 views

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

asked Dec 7, 2017 at 6:28

0 votes

0 answers

96 views

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

asked Sep 15, 2017 at 20:06

2 votes

2 answers

113 views

Do we know something about this refutation method for SAT?

asked Sep 13, 2017 at 22:33

1 vote

0 answers

111 views

Is such variant of SAT always satisfiable?

asked Sep 10, 2017 at 22:11

3 votes

1 answer

425 views

Linear time multiplication on RAM machine?

asked Sep 9, 2017 at 0:27

1 vote

1 answer

49 views

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

asked Sep 8, 2017 at 10:41

0 votes

1 answer

167 views

Another way to solve SAT. Was it known?

asked Sep 7, 2017 at 9:16

1 vote

1 answer

63 views

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

asked Sep 6, 2017 at 0:54

2 votes

3 answers

5k views

3-SAT with 3 variable occurences

asked Sep 5, 2017 at 8:22

2 votes

1 answer

51 views

2CNF with 3 variable occurences

asked Sep 1, 2017 at 6:27

1 vote

0 answers

66 views

Determining when equal 2CNF has pure literal

asked Aug 31, 2017 at 21:52

1 vote

1 answer

98 views

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

asked Aug 31, 2017 at 0:55

3 votes

1 answer

200 views

Is boolean formula isomorphism NP-complete?

asked Aug 28, 2017 at 1:49

Stack Exchange Network

54 Questions

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

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

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

A machine with multiple oracles

Is it an open problem if CDCL algorithms violate SETH?

Schaefer's dichotomy theorem and limits on the formula length

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

Exponential Time Hypothesis and the input size vs number of variables

Universal quantification and the number of solutions

Assuming $\mathsf{P=BPP}$ would it be possible to derandomize the verifier in Interactive Proof systems?

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?