We define DLOGTIME proof systems, DLTPS, which generalize NC~0 proof systems. It is known that functions such as Exactk and Majority do not have NC~0 proof systems. Here， we give a DLTPS for Exactk (and therefore for Majority) and also for other natural functions such as Reach and Cliquek.. Though many interesting functions have DLTPS, we show that there are languages in NP which do not have DLTPS. We consider the closure properties of DLTPS and prove that they are closed under union and concatenation but are not closed under intersection and complement. Finally, we consider a hierarchy of polylogarithmic time proof systems and show that the hierarchy is strict.
展开▼
