Name
Abstract | ||
|---|---|---|
Characterizations of nondeterministic complexity classes such as NP and PSPACE and the classes in the polynomial-time hierarchy in the two-person pebble game model are given. It is shown that the role-switches resource in the pebble games closely models the levels of the polynomial hierarchy. These characterizations are made possible by explicitly considering circuit size in the pebbling characterizations and the size of the underlying universe in the first-order characterizations. A dual interpreted game to model parallel computations was defined by H. Venkateswaran et al. (1986). They used this game to obtain characterizations of parallel complexity classes such as LOGCFL and AC1. This result is extended to obtain characterizations of the class NP and the classes in the polynomial-time hierarchy in the game model. The role switches resource was used in the dual game to capture the difference between computations in the classes LOGCFL and AC1. It is shown that role-switches model the alternating time hierarchy more accurately, and thus their collapse implies the collapse of hierarchies such as the polynomial-time hierarchy. Specifically, it is shown that the kth level of the polynomial-time hierarchy uses k-1 role-switches |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1109/SCT.1990.113970 | Structure in Complexity Theory Conference |
Keywords | Field | DocType |
circuit size,nondeterministic complexity classes,automata theory,parallel computations,pebbling,parallel programming,logcfl,expressibility,np,pspace,computational complexity,game theory,two-person pebble game model,role switches resource,polynomial-time hierarchy,ac1,circuits,complexity class,polynomials,computer science,parallel computer,first order,polynomial time,robustness,automation | Complexity class,Polynomial hierarchy,Discrete mathematics,Combinatorics,Nondeterministic algorithm,LOGCFL,PSPACE,Game theory,Hierarchy,Mathematics,Computational complexity theory | Conference |
Citations | PageRank | References |
1 | 0.38 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Vinay | 1 | 48 | 6.38 |
| H. Venkateswaran | 2 | 1 | 0.38 |
| C. E. Veni Madhavan | 3 | 366 | 82.05 |