Jozef's user avatar
Jozef's user avatar
Jozef's user avatar
Jozef
  • Member for 11 years, 10 months
  • Last seen more than 9 years ago
27 votes
4 answers
18k views

Finding the minimum cut of an undirected graph

19 votes
2 answers
16k views

Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?

15 votes
2 answers
11k views

Is it decidable whether a TM reaches some position on the tape?

14 votes
2 answers
2k views

Closure against right quotient with a fixed language

14 votes
1 answer
453 views

For a Turing Machine $M_1$, how is the set of machines $M_2$ which are "shorter" than $M_1$ and which accept the same language decidable?

8 votes
1 answer
252 views

How to show that the set of machines which accept languages in $\mathrm{NP}\smallsetminus\mathrm P$, is decidable only if $\mathrm P=\mathrm{NP}$?

7 votes
4 answers
546 views

Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

6 votes
3 answers
10k views

Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

5 votes
1 answer
442 views

The operator $A(L)= \{w \mid ww \in L\}$

5 votes
3 answers
3k views

Proving that recursively enumerable languages are closed against taking prefixes

5 votes
2 answers
466 views

Is $A=\{ w \in \{a,b,c\}^* \mid \#_a(w)+ 2\#_b(w) = 3\#_c(w)\}$ a CFG?

5 votes
1 answer
2k views

Chomsky normal form and regular languages

5 votes
1 answer
410 views

Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

4 votes
2 answers
1k views

$L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

4 votes
1 answer
120 views

For a graph $G$ find the minimal $t$ such $G(t)=(V,E(t))$ is connected

4 votes
1 answer
2k views

Equality of NSpace and coNSpace classes

3 votes
1 answer
215 views

Find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one)

2 votes
1 answer
106 views

Concluding $SPACE(n^2) \neq SPACE(n^7)$ from universal turing machine running time

1 vote
1 answer
279 views

BPP clarification

1 vote
1 answer
494 views

Gap problems clarifation

1 vote
1 answer
219 views

How come this turing machine running time is $O(n^{1+\log_2 2006}\cdot \log_2n)$

1 vote
1 answer
213 views

For what values of A and B is the gap-VC-[A,B] problem NP-HARD?