Skip to main content
MathOverflow

Return to Question

deleted 58 characters in body
Source Link
Liron
Liron
  • 213
  • 2
  • 9

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

Obviously it contains Sigma2 union Pi2, but what else?

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

Obviously it contains Sigma2 union Pi2, but what else?

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

deleted 76 characters in body; edited tags; edited title
Source Link
Ben Webster ♦
Ben Webster ♦
  • 44.7k
  • 12
  • 126
  • 260

Characterize How can one characterize NP^SAT?

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

Obviously it contains Sigma2 union Pi2, but what else?

Btw someone should create a Complexity tag; I can't do it since I'm a new user.

Characterize NP^SAT

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

Obviously it contains Sigma2 union Pi2, but what else?

Btw someone should create a Complexity tag; I can't do it since I'm a new user.

How can one characterize NP^SAT?

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

Obviously it contains Sigma2 union Pi2, but what else?

Source Link
Liron
Liron
  • 213
  • 2
  • 9

Characterize NP^SAT

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

Obviously it contains Sigma2 union Pi2, but what else?

Btw someone should create a Complexity tag; I can't do it since I'm a new user.