Questions tagged [intuition]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
19
votes
5answers
3k views

Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?

It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$. This can easily be understood inductively using oracle machines. The question ...
27
votes
6answers
2k views

How do you get a "Physical Intuition" for results in TCS?

I'm sorry if this question is a little vague, but I am curious how successful researchers get a "feel" for the results in TCS. For example, linear algebra can be understood geometrically, or in terms ...