12

Questions
votes newest views recent
1
7
votes
1
answer
200
views

Defining measures over frames in place of $\sigma$-algebras

feb 2 at 2:27 Tom LaGatta 4,340●6●19

2
6
votes
2
answers
424
views

Natural statements independent from true $\Pi^0_2$ sentences

nov 9 at 22:26 Julian Fernandez 83●5

 
3
votes
1
answer
166
views

History of provably total functions of a theory

jun 27 at 5:03 Zhang Jing 309●1●1●6

12
21
votes
3
answers
2k
views

Can we cover the unit square by these rectangles?

jun 23 at 12:37 Denis Serre 18.7k●1●31●93

1
2
votes
0
answers
162
views

Oracle sparating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on DDH)

jul 16 11 at 6:48 Kaveh 2,187●5●24

6
11
votes
1
answer
2k
views

How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?

aug 27 10 at 12:39 Kaveh 2,187●5●24

4
17
votes
2
answers
770
views

Is there a syntactic characterization for BPP, BQP, or QMA?

aug 12 10 at 0:18 Robin Kothari 918●4●11

2
5
votes
3
answers
1k
views

When would you read a paper claiming to have settled a long open problem like $P$ vs. $NP$? [closed]

aug 8 10 at 23:55 Oryx_Crake 1

7
11
votes
5
answers
946
views

What are the most important results (and papers) in complexity theory that every one should know?

aug 5 10 at 18:24 Ryan Williams 3,126●6●25

5
9
votes
0
answers
924
views

Razborov’s response to Almost Natural Proofs

jul 31 10 at 22:23 Kaveh 2,187●5●24

1 2 next