Skip to main content
rus9384's user avatar
rus9384's user avatar
rus9384's user avatar
rus9384
  • Member for 7 years, 2 months
  • Last seen this week
1 vote
1 answer
36 views

How many minimal graphs on $n$ vertices with radius and diameter of 2 are there?

1 vote
1 answer
48 views

Is this graph grouping problem $\mathsf{NP}$-hard?

2 votes
0 answers
31 views

Complexity of strong graph realization problem

2 votes
1 answer
56 views

Number of graphs that almost contain a $k$-clique

1 vote
0 answers
21 views

$\mathsf{NP}$ vs. $\mathsf{coNP}$ and sparse sets

0 votes
1 answer
88 views

Is it an open problem if CDCL algorithms violate SETH?

3 votes
1 answer
38 views

Is boolean formula equivalence problem for 2-CNFs $\mathsf{coNP}$-hard?

0 votes
0 answers
25 views

Effectively universal Turing machines and Turing-completeness?

0 votes
1 answer
39 views

Undecidability of the exactly-1-in-k halting problem

5 votes
0 answers
163 views

Can minimal CNF contain clause longer than initial CNF?

1 vote
1 answer
44 views

Is it possible to find reductions from problems in $\mathsf{NP}$ to SAT based solely on the certificate verification algorithm?

1 vote
0 answers
23 views

CNF Horn-renamability to 3-CNF Horn-renamability reduction?

1 vote
1 answer
33 views

What would be the consequences of TQBF having polynomial length winning instructions?

0 votes
0 answers
17 views

Does $\mathsf{NC_1\subsetneq NC}$ imply $\mathsf{NP\neq coNP}$?

0 votes
1 answer
35 views

Does Cutting Planes solve Pigeongole Principle for holes of different sizes?

2 votes
1 answer
197 views

Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT

0 votes
0 answers
28 views

Is it possible to perform clause-pair minimization on a CNF instance in $o(n^2)$ time?

1 vote
0 answers
44 views

Is $\mathsf P$ low for every complexity class between itself and $\mathsf{NP}$?

1 vote
0 answers
24 views

Are there any SAT outside of $\mathsf{RP}$ variants that are solvable in quasipolynomial time?

2 votes
0 answers
18 views

Properties of $\mathsf{PH}[1]$ and $\Sigma^{\mathsf P}_{poly(n)}[1]$?

1 vote
1 answer
23 views

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

0 votes
1 answer
30 views

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

1 vote
0 answers
31 views

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

0 votes
1 answer
31 views

A machine with multiple oracles

-1 votes
1 answer
48 views

Schaefer's dichotomy theorem and limits on the formula length

2 votes
3 answers
6k views

3-SAT with 3 variable occurences

1 vote
1 answer
66 views

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

2 votes
2 answers
175 views

Exponential Time Hypothesis and the input size vs number of variables

3 votes
0 answers
57 views

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

0 votes
1 answer
57 views

Universal quantification and the number of solutions