Skip to main content
Vanessa's user avatar
Vanessa's user avatar
Vanessa's user avatar
Vanessa
  • Member for 12 years, 8 months
  • Last seen this week
29 votes
3 answers
1k views

Is NPI contained in P/poly?

18 votes
0 answers
356 views

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

15 votes
0 answers
459 views

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

12 votes
1 answer
497 views

Optimal NP solvers

12 votes
2 answers
624 views

Efficient universal problem solver?

9 votes
0 answers
265 views

Are there sampNP-intermediate problems?

9 votes
1 answer
388 views

"Verifiable information": is this a known concept?

9 votes
0 answers
514 views

Assigning probability to membership in an NP-complete language

8 votes
1 answer
430 views

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

7 votes
0 answers
168 views

Universal tractable problem solver

6 votes
1 answer
185 views

How big is NSC^k?

6 votes
2 answers
4k views

Complexity of the halting problem

5 votes
0 answers
243 views

Non-uniform average-case complexity of NP

5 votes
0 answers
254 views

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

5 votes
0 answers
204 views

Easy interactive proofs for easy problems?

5 votes
1 answer
302 views

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

4 votes
1 answer
167 views

What is the etiquette of naming concepts after people?

4 votes
1 answer
380 views

Quantum cellular automata

3 votes
1 answer
302 views

Are randomly generated infinite patterns computable?

3 votes
1 answer
174 views

Speed-up of universal computation by caching

3 votes
0 answers
148 views

Existence of complete "asymptotic" optimization problems

3 votes
0 answers
78 views

Solving MDPs with polytope action spaces

2 votes
0 answers
201 views

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

2 votes
0 answers
80 views

Efficient asympotically universal predictors

2 votes
3 answers
321 views

Complexity of universal computation on random input

1 vote
1 answer
165 views

Average performance of universal computation

1 vote
0 answers
104 views

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

1 vote
0 answers
52 views

Circuit games in extensive form with imperfect information