One-Way Functions and the Nonisomorphism of NP-Complete Sets.
Juris HartmanisLane A. HemachandraPublished in: Theor. Comput. Sci. (1991)
Keyphrases
- np complete
- semi algebraic
- randomly generated
- computational complexity
- satisfiability problem
- np hard
- logical equivalence
- database
- polynomial time complexity
- upper bound
- pspace complete
- conjunctive queries
- set theoretic
- phase transition
- bounded treewidth
- sat problem
- convex sets
- basis functions
- constraint satisfaction problems
- information retrieval
- real world
- real time