User rus9384

0 votes

1 answer

54 views

Is it an open problem if CDCL algorithms violate SETH?

asked Jul 8 at 23:13

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

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

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

-1 votes

1 answer

36 views

Schaefer's dichotomy theorem and limits on the formula length

asked Jul 7 at 14:06

2 votes

3 answers

5k views

3-SAT with 3 variable occurences

asked Sep 5, 2017 at 8:22

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

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

0 votes

1 answer

53 views

Universal quantification and the number of solutions

asked May 10, 2022 at 23:43

3 votes

1 answer

118 views

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

asked Aug 9, 2017 at 13:15

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

4 votes

0 answers

122 views

Can minimal CNF contain clause longer than initial CNF?

asked Jun 17, 2017 at 12:57

2 votes

2 answers

113 views

Do we know something about this refutation method for SAT?

asked Sep 13, 2017 at 22:33

3 votes

1 answer

200 views

Is boolean formula isomorphism NP-complete?

asked Aug 28, 2017 at 1:49

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

3 votes

1 answer

425 views

Linear time multiplication on RAM machine?

asked Sep 9, 2017 at 0:27

1 vote

0 answers

111 views

Is such variant of SAT always satisfiable?

asked Sep 10, 2017 at 22:11

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

1 vote

0 answers

66 views

Determining when equal 2CNF has pure literal

asked Aug 31, 2017 at 21:52

Stack Exchange Network

54 Questions

Is it an open problem if CDCL algorithms violate SETH?

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

Schaefer's dichotomy theorem and limits on the formula length

3-SAT with 3 variable occurences

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

Exponential Time Hypothesis and the input size vs number of variables

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

Universal quantification and the number of solutions

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

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

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