Name: Circuit definitions of nondeterministic complexity classes
Creator: Venkateswaran, H.
Keywords: nondeterministic space and time classes, 4. Education, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), 0102 computer and information sciences, 02 engineering and technology, Models of computation (Turing machines, etc.), skew circuits, 16. Peace & justice, 01 natural sciences, arithmetic circuit

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Article 01 Jan 1988Publisher:Springer Berlin HeidelbergJournal:SIAM Journal on Computing, volume 21, pages 655-670 (issn: 0097-5397, eissn: 1095-7111,

Authors: Venkateswaran, H.;

doi: 10.1007/3-540-50517-2_80 , 10.1137/0221040

Circuit definitions of nondeterministic complexity classes

- Summary
- Subjects
- Metrics

Abstract

Summary: This paper considers restrictions on Boolean circuits and uses them to obtain new uniform circuit characterizations of nondeterministic space and time classes. It also obtains characterizations of counting classes based on nondeterministic time bounded computations on the arithmetic circuit model. It is shown how the notion of semi-unboundedness unifies the definitions of many natural complexity classes.

Related Organizations

Keywords

nondeterministic space and time classes, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Models of computation (Turing machines, etc.), skew circuits, arithmetic circuit, Complexity classes (hierarchies, relations among complexity classes, etc.), semi-unboundedness, Circuits, networks, Boolean circuits

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	38
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average