Skip to main content
Haskell Fun's user avatar
Haskell Fun's user avatar
Haskell Fun's user avatar
Haskell Fun
  • Member for 6 years, 11 months
  • Last seen more than 6 years ago
5 votes
1 answer
4k views

Show that if $NP\subseteq BPP$ then also $NP=RP$ - considerations about solution

3 votes
1 answer
759 views

Why we can't use non-deterministic turing machines in this case?

2 votes
1 answer
1k views

Prove that $L$ is closed under Kleene star iff $L=NL$

2 votes
2 answers
512 views

Prove that checking if context free grammar generates word with all symbols is NP-complete - unclear statement about encoing probem in exercise

1 vote
1 answer
59 views

Prove that following graph problem is in $L$

1 vote
1 answer
357 views

Show that problem is PSPACE-complete - path in directed graph

1 vote
1 answer
288 views

Confusing method of proving PSPACE-completness

1 vote
2 answers
2k views

Show that (2,3)-satisfability is np-complete

1 vote
2 answers
152 views

Find $i$-th number in unsorted sequence in logspace (deterministic turing machine)

1 vote
2 answers
576 views

Solving $UCYCLE$ in logspace - two possible approaches ? Why can't we one of them use to solve connectivity?

1 vote
2 answers
495 views

Show that boring boolean circuit belongs to NP-complete class

1 vote
2 answers
4k views

A problem is NP-hard iff its complement is coNP-complete

0 votes
1 answer
202 views

How does it possible that $ZPP=RP\cap coRP$?

0 votes
1 answer
85 views

Does there exist a language which is PSPACE-complete and regular?

0 votes
1 answer
62 views

Show that checking if there exists word not containg patterns from list is in $PSPACE$

0 votes
0 answers
175 views

P-complete problem due to logspace reductions. What does it mean?

0 votes
1 answer
55 views

Find isomorphism of graph with maximal number $x$ such that $f(x)\neq x$ - assuming $NP=P$

0 votes
0 answers
55 views

Show that if language belongs to $BPP$ then also similar language belgons to $QP$

0 votes
0 answers
58 views

Check if $NP ⊆ BPP $

0 votes
0 answers
234 views

Check if class $PSPACE$ is closed under polyonomially space reduction

-1 votes
1 answer
317 views

Graph isomorphism in BPP implies it is also in RP