rus9384's user avatar
rus9384's user avatar
rus9384's user avatar
rus9384
  • Member for 6 years, 7 months
  • Last seen this week
1 vote
1 answer
19 views

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

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?

1 vote
0 answers
29 views

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

0 votes
1 answer
26 views

A machine with multiple oracles

0 votes
1 answer
54 views

Is it an open problem if CDCL algorithms violate SETH?

-1 votes
1 answer
36 views

Schaefer's dichotomy theorem and limits on the formula length

1 vote
1 answer
59 views

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

2 votes
2 answers
155 views

Exponential Time Hypothesis and the input size vs number of variables

0 votes
1 answer
53 views

Universal quantification and the number of solutions

3 votes
0 answers
56 views

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

1 vote
0 answers
27 views

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

0 votes
0 answers
39 views

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

1 vote
0 answers
179 views

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

2 votes
1 answer
123 views

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

1 vote
2 answers
75 views

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

1 vote
0 answers
45 views

Are complexity classes equal in this case?

3 votes
0 answers
44 views

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

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?

0 votes
0 answers
96 views

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

2 votes
2 answers
113 views

Do we know something about this refutation method for SAT?

1 vote
0 answers
111 views

Is such variant of SAT always satisfiable?

3 votes
1 answer
425 views

Linear time multiplication on RAM machine?

1 vote
1 answer
49 views

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

0 votes
1 answer
167 views

Another way to solve SAT. Was it known?

1 vote
1 answer
63 views

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

2 votes
3 answers
5k views

3-SAT with 3 variable occurences

2 votes
1 answer
51 views

2CNF with 3 variable occurences

1 vote
0 answers
66 views

Determining when equal 2CNF has pure literal

1 vote
1 answer
98 views

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

3 votes
1 answer
200 views

Is boolean formula isomorphism NP-complete?