On the Polyhedral Decision Problem

DOI10.1137/0209028MaRDI QIDQ3893331zbMATH OpenOpenAlexFDO

Authors Andrew Chi-Chih Yao, Ronald L. Rivest

Publication date 1980

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0209028

zbMATH Keywords

lower boundlinear decision treeadversary strategypolyhedral decision problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cited in

(14)

• Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
• Decision trees: Old and new results.
• A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems
• Lower bounds on probabilistic linear decision trees
• Complexity lower bounds for computation trees with elementary transcendental function gates
• Legal coloring of graphs
• Monotonicity checking
• Testing the optimality of alphabetic trees
• Comparisons between linear functions can help
• Nearly sharp complexity bounds for multiprocessor algebraic computations
• Structure of a simple scheduling polyhedron
• On the decisional complexity of problems over the reals
• Algebraic decision trees and Euler characteristics
• Lower bound on testing membership to a polyhedron by algebraic decision and computation trees

This page was built for publication: On the Polyhedral Decision Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3893331)