(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the nu …

The standard way to show that a problem is NP-complete is to show that another problem known to be NP-complete reduces to it. That much is clear. Given a problem in NP, what's kn …

Luca Trevisan here gives a randomized polynomial-time approximation algorithm for #3-coloring given an NP oracle. In a similar vein, I was wondering if there were any results on $ …

What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic program …

Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far …

What can you say about the complexity class P^NP, i.e. decision problems solvable by a polytime TM with an oracle for SAT? Obviously P^NP is in PH somewhere between NP union coNP, …

Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?