Non deterministic polynomial optimization problems and their approximations
type: Item
instance of: scholarly article
title: Non deterministic polynomial optimization problems and their approximations
zbMATH Open document ID: 0459.68015
DOI: 10.1016/0304-3975(81)90081-5
author: S. H. Smith
published in: Theoretical Computer Science
publication date: 1981-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3720353
MaRDI profile type: Publication
full work available at URL: 0304-3975(81)90081-5
OpenAlex ID: W2056090079
cites work: On the computational power of pushdown automata
cites work: Q4198057
cites work: The complexity of theorem-proving procedures
cites work: Q4161330
cites work: The Complexity of Near-Optimal Graph Coloring
cites work: `` Strong '' NP-Completeness Results
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Q4077442
cites work: Q4142699
cites work: Applications of a Planar Separator Theorem
cites work: General approximation algorithms for some arithmetical combinatorial problems
cites work: Q4125769
cites work: Q4146536
cites work: Q4164569
cites work: Computationally Related Problems
cites work: Combinatorial Problems: Reductibility and Approximation
cites work: P-Complete Approximation Problems
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: A Fast Monte-Carlo Test for Primality
description: scientific article; zbMATH DE number 3720353