|
|
|
|
|
NexptimeIn computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(2p(n)) for some polynomial p(n), and unlimited space. In terms of NTIME, -
An important set of NEXPTIME-complete problems relates to succinct circuits. Succinct circuits are simple machines used to describe graphs in exponentially less space. They accept two vertex numbers as input and output whether there is an edge between them. If solving a problem on a graph in a natural representation, such as an adjacency matrix, is NP-complete, then solving the same problem on a succinct circuit representation is NEXPTIME-complete, because the input is exponentially smaller.1 As one simple example, finding a Hamiltonian path for a graph thus encoded is NEXPTIME-complete. References C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0201530821. Footnotes 1. Papadimitriou, section 20.1, pg.492.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|