On the Polyhedral Decision Problem

DOI10.1137/0209028zbMath0447.68076OpenAlexW2140515217MaRDI QIDQ3893331

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)

Related Items (14)

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

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