
\newtheorem{theo}{Theorem}[section]
\newtheorem{claim}{Claim}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{coro}{Corollary}[section]
\newtheorem{defi}{Definition}
\newtheorem{fact}{Fact}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{theorem}{Theorem}[section]

\newcommand{\p}{{\rm P}}
\newcommand{\PL}{{\rm PL}}
\newcommand{\E}{{\rm E}}
\newcommand{\EXP}{{\rm EXP}}

\newcommand{\NP}{{\rm NP}}
\newcommand{\NPL}{{\rm NPL}}
\newcommand{\NEXP}{{\rm NEXP}}
\newcommand{\NE}{{\rm NE}}

\newcommand{\PH}{{\rm PH}}
\newcommand{\EXPH}{{\rm EXPH}}
\newcommand{\SEXPH}{{\rm SEXPH}}

\newcommand{\PF}{{\rm PF}}
\newcommand{\aalt}{{\rm ATIME \! - \! ALT}}
\newcommand{\saalt}{{\rm ATIME \! - \! ALT!}}
\newcommand{\sigmaexpi}{{\rm \Sigma^{\EXP}_i}}
  
\newcommand{\cin}{\in_c}
\newcommand{\csubseteq}{\subseteq_c}
\newcommand{\xsubsetneq}{\not\subseteq}
\newcommand{\subsetneq}{
	\mbox{ \raisebox{.4ex}{$\subset$} 
	\hspace{-.15in}\rule[-.03in]{.09in}{.01in}
	\hspace{-.1in}\rule[-.06in]{.01in}{.05in}
	\hspace{.001in}
	}}
\newcommand{\co}{co \! - \!}
\newcommand{\KSIG}{K_{\Sigma^{\EXP}_i}}
\newcommand{\KD}{D}
\newcommand{\ke}{K_{\Sigma^{EXP}_1}}
\newcommand{\nke}{\overline{\ke}}
\newcommand{\sans}{SAT \wedge \overline{SAT}}
\newcommand{\nsos}{\overline{SAT} \vee SAT}
\newcommand{\trip}{\langle e, \, x, \, t \rangle}
\newcommand{\onetrip}{\langle e_1, \, x_1, \, t_1 \rangle}
\newcommand{\twotrip}{\langle e_2, \, x_2, \, t_2 \rangle}
\newcommand{\ftrip}{(\langle e, \, x, \, t \rangle_1, \,
		     \langle e, \, x, \, t \rangle_2)}
\newcommand{\strip}{(\langle e, \, x, \, t \rangle_3, \,
		     \langle e, \, x, \, t \rangle_4)}
\newcommand{\kank}{\ke \wedge \overline{\ke}}
\newcommand{\nkok}{\overline{\ke} \vee \ke}

\newcommand{\natN}{\rm N} 
% \newcommand{\natN}{{\sf N\hspace*{-0.9ex} \rule{0.15ex} %
% {1.5ex}\hspace*{0.9ex}}}
\newcommand{\eop}{\hspace*{\fill} {\Large $\Box$} \vspace{24truept}}
\newcommand{\proof}{\noindent {\bf Proof.} \, }
\newcommand{\proofofclaim}{\noindent {\bf Proof of Claim.} \, }
\newcommand{\proofoutline}{\noindent {\bf Proof Outline.} \, }

\newcommand{\rmP}[2]{#1^{\rm P}_{#2}}
\newcommand{\rmNP}[2]{#1^{\rm NP}_{#2}}
\newcommand{\rmC}[2]{#1^{\rm C}_{#2}}
\newcommand{\m}{\mbox{$\rmP{\leq}{m}$}}
\newcommand{\mNP}{\mbox{$\rmNP{\leq}{m}$}}
\newcommand{\trtable}[1]{\rmP{\leq}{#1 \mbox{\scriptsize\it{-tt}}}}
\newcommand{\disj}[1]{\leq_{#1 \mbox{\scriptsize\it{-disj}}}}
\newcommand{\truth}{\rmP{\leq}{\mbox{\scriptsize\it{tt}}}}
\newcommand{\ctruth}{\rmC{\leq}{\mbox{\scriptsize\it{tt}}}}
\newcommand{\exptt}{\EXP{\leq}{\mbox{\scriptsize\it{tt}}}}
% \newcommand{\NEXP1}{\rmNEXP^{\rmNP [1]}}
\newcommand{\T}{\rmP{\leq}{T}}
\newcommand{\cT}{\rmC{\leq}{T}}

\newcommand{\st}{\,|\,}
\newcommand{\lb}{ \; | \; } 
\newcommand{\cs}{ , \; } 
\newcommand{\ifff}{\Longleftrightarrow} 


