Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-167 | 21st November 2019 01:52

UTIME Easy-witness Lemma & Some Consequences


Authors: Anant Dhayal, Russell Impagliazzo
Publication: 21st November 2019 03:41
Downloads: 183


We prove an easy-witness lemma ($\ewl$) for unambiguous non-deterministic verfiers. We show that if $\utime(t)\subset\mathcal{C}$, then for every $L\in\utime(t)$, for every $\utime(t)$ verifier $V$ for $L$, and for every $x\in L$, there is a certificate $y$ satisfing $V(x,y)=1$, that can be encoded as a truth-table of a $\mathcal{C}$ circuit. Our technique is simple compared to the $\ntime$ $\ewl$s \cite{IKW02,Wil-ES13,MW18}, and yields fine-grained results in terms of the time and size parameters. It also works for all {\it typical} non-uniform circuit classes without any additional machinery. Using this $\ewl$ we prove a Karp-Lipton \cite{KL80} style theorem ($\klt$) for $\uexp$. We show that $\uexp\subset\size(poly)\implies\uexp=\ma$. We also prove similar $\ewl$ and $\klt$ for $\uexp\cap\couexp$ and $\fewexp$.

Circuit lower bound techniques that entail natural properties of Razborov and Rudich \cite{RR97} are called natural, and are known to contradict widely believed cryptographic assumptions in the course of proving strong lower bounds. Thus attempts have been made to understand un-natural techniques. Natural properties satisfy three conditions: usefulness, constructiveness, and largeness. Usefulness is unavoidable in any lower-bound technique. In \cite{Wil-NP16,Ig13} it was shown that obtaining $\nexp$ lower bounds is equivalent to obtaining $\pt$-constructive (with $\log n$ advice) properties.

In this paper we consider properties that avoid largeness. We introduce a new notion called unique properties, which is opposite to natural properties in the sense of largeness. A unique property contains exactly one element of each input length (that is a power of 2). We show that $\pt$-constructivity and uniqueness (opposite of largeness) both are unavoidable for certain lower bounds. We prove, $\uexp\cap\couexp\not\subset\mathcal{C}$ if and only if there is a $\pt$-constructive unique property against $\mathcal{C}$. We also establish equivalences between lower bounds against $\uexp$ (with and without advice), and the existence of different restrictions of $\pt$-constructive unique properties that use advice.

The ``derandomization (of $\bpp$) from uniform/non-uniform lower bounds for $\Gamma$'' type of results are known for $\Gamma=\expo,\nexp,\nexp\cap\conexp,\rexp$ \cite{NW94,BFNW93,IW01,IKW02,Wil-NP16}. Using the above equivalences we obtain a super-set of these results that also includes the classes $\uexp,\uexp\cap\couexp,\zpexp$.

One important application of the $\nexp$ $\ewl$ and $\klt$ is the connection between fast ($\sat$ and learning) algorithms and $\nexp$ lower bounds \cite{Wil-ES13,FK09,Ig13}. Using our $\utime$ $\ewl$ and $\klt$ we derive connections between fast unambiguous algorithms and $\utime$ lower bounds. Finally we show results that generalize the lower bound frameworks -- that work only for unrestricted Boolean circuits -- such that they work for any restricted typical circuit class. This will help us to get lower bounds against any typical circuit class from fast algorithms that work for that particular class (and not for the super-class of unrestricted Boolean circuits).

ISSN 1433-8092 | Imprint