Preliminaries - Repairing and Querying Databases under Aggregate Constraints - page 22

• PTIME : the class of decision problems which are solvable in polynomial time by

deterministic Turing Machines. This class is also denoted as P ;

•

NP : the class of decision problems which are solvable in polynomial time by
nondeterministic Turing Machines;

• co NP : the class of decision problems whose complements are in NP ;

• Σ

p
2 : the class of decision problems which are solvable in polynomial time by
nondeterministic Turing machines with an NP oracle. This class is also denoted
as NP NP ;
• Π

p
2 : the class of decision problems whose complements are in

p
2 . This class is

Σ

also denoted as coNP NP ;
• Δ

p
2 : the class of decision problems which are solvable in polynomial time by
deterministic Turing machines with an NP oracle. This class is also denoted as
P NP ;
• Δ

p
2 [

: the class of decision problems which are solvable in polynomial time
by deterministic Turing machines with an NP oracle invoked O

log ( n )]

( log ( n )) times.

This class is also denoted as P NP [ log ( n )] ;