Network profile

Numerator

Reputation

442

442
432
422

2018
2019
2020
2021

Top tag

computability

Next privilege

500 Rep.

Access review queues

Badges

2

8

Newest

Yearling

Next badge

0/1

Impact

0 posts edited

0 helpful flags

13 votes cast

6 Questions

Votes Activity Newest Views

9

votes

1

answer

760

views

Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable

formal-languages computability context-free turing-machines

May 22 '12 at 1:10 Carl Mummert 2,023

3

8

votes

1

answer

700

views

Prove or refute: BPP(0.90,0.95) = BPP

complexity-theory time-complexity probabilistic-algorithms

Jan 8 '13 at 19:20 Steven Stadnicki 2,302

8

votes

3

answers

555

views

Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable?

computability turing-machines

Jun 10 '12 at 20:19 Ran G. 19.4k

1

7

votes

2

answers

936

views

Is SAT in P if there are exponentially many clauses in the number of variables?

complexity-theory np-complete reductions satisfiability polynomial-time

Jul 21 '12 at 19:06 Community♦ 1

6

votes

1

answer

433

views

Show that the halting problem is decidable for one-pass Turing machines

formal-languages computability turing-machines check-my-proof

Jan 18 '13 at 9:58 vonbrand 12.6k

1

5

votes

2

answers

341

views

randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $\frac{2}{3}$

complexity-theory time-complexity randomized-algorithms

Jan 5 '13 at 20:18 Numerator 442

Computer Science Stack Exchange works best with JavaScript enabled