We prove an easy-witness lemma ( \ewl ) for unambiguous non-deterministic verfiers. We show that if \utime ( t ) , then for every L \utime ( t ) , for every \utime ( t ) verifier V for L , and for every x L , there is a certificate y satisfing V ( x y ) = 1 , that can be encoded as a truth-table of a 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 \size ( pol y ) \implies \uexp = \ma . We also prove similar \ewl and \klt for \uexp \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 \couexp if and only if there is a \pt -constructive unique property against . 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 '' type of results are known for = \expo \nexp \nexp \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 \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).