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
768 views

SAT to knapsack vs. ETH

1 vote
1 answer
49 views

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

1 vote
1 answer
98 views

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

1 vote
0 answers
66 views

Determining when equal 2CNF has pure literal

1 vote
0 answers
111 views

Is such variant of SAT always satisfiable?

1 vote
1 answer
59 views

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

1 vote
0 answers
29 views

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

1 vote
1 answer
20 views

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

1 vote
0 answers
179 views

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

1 vote
0 answers
45 views

Are complexity classes equal in this case?

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
27 views

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

0 votes
1 answer
53 views

Universal quantification and the number of solutions

0 votes
0 answers
39 views

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

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?

0 votes
1 answer
54 views

Is it an open problem if CDCL algorithms violate SETH?

0 votes
1 answer
26 views

A machine with multiple oracles

0 votes
0 answers
96 views

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

0 votes
1 answer
94 views

Understanding kQBF: changing order of quantification?

0 votes
1 answer
167 views

Another way to solve SAT. Was it known?

0 votes
1 answer
61 views

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

0 votes
1 answer
381 views

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

0 votes
1 answer
208 views

Colored cliques complexity

-1 votes
1 answer
36 views

Schaefer's dichotomy theorem and limits on the formula length

1
2