Vanessa's user avatar
Vanessa's user avatar
Vanessa's user avatar
Vanessa
  • Member for 12 years, 5 months
  • Last seen more than a month ago
6 votes
2 answers
4k views

Complexity of the halting problem

29 votes
3 answers
1k views

Is NPI contained in P/poly?

12 votes
2 answers
621 views

Efficient universal problem solver?

9 votes
0 answers
513 views

Assigning probability to membership in an NP-complete language

12 votes
1 answer
496 views

Optimal NP solvers

15 votes
0 answers
456 views

What is the evidence for average case separation between EXP and NEXP?

8 votes
1 answer
430 views

Is $\mathsf{P} = \mathsf{NP}$ relative to a universal predictor?

9 votes
1 answer
388 views

"Verifiable information": is this a known concept?

4 votes
1 answer
380 views

Quantum cellular automata

18 votes
0 answers
354 views

$\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$? [duplicate]

2 votes
3 answers
320 views

Complexity of universal computation on random input

3 votes
1 answer
302 views

Are randomly generated infinite patterns computable?

5 votes
1 answer
300 views

Is Bayes optimal RL of a finite set of DFAs feasible?

9 votes
0 answers
265 views

Are there sampNP-intermediate problems?

5 votes
0 answers
253 views

Is Solomonoff Induction in $\mathsf{P/poly}$?

5 votes
0 answers
242 views

Non-uniform average-case complexity of NP

5 votes
0 answers
203 views

Easy interactive proofs for easy problems?

2 votes
0 answers
199 views

Two-player zero-sum games in extensive form represented as directed acyclic graphs

6 votes
1 answer
185 views

How big is NSC^k?

3 votes
1 answer
172 views

Speed-up of universal computation by caching

7 votes
0 answers
168 views

Universal tractable problem solver

4 votes
1 answer
167 views

What is the etiquette of naming concepts after people?

1 vote
1 answer
164 views

Average performance of universal computation

3 votes
0 answers
148 views

Existence of complete "asymptotic" optimization problems

1 vote
0 answers
104 views

Universal predictor for $\mathsf{L}$-sequences in $\mathsf{P}$?

2 votes
0 answers
80 views

Efficient asympotically universal predictors

3 votes
0 answers
78 views

Solving MDPs with polytope action spaces

1 vote
0 answers
52 views

Circuit games in extensive form with imperfect information