Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model

DOI10.1007/BF02218439zbMath0512.90076OpenAlexW1975384529MaRDI QIDQ1050255

Esko Ukkonen

Publication date: 1983

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02218439

zbMATH Keywords

exponential lower boundsNP-completeness23, 181-192 (1983)linear recognition problemlinear test functionslower bounds on the number of comparisonsrestricted linear decision tree modelternary comparisons

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Related Items

Lower bound arguments with ``inaccessible numbers, Lower bounds for sorting of sums, Stability versus speed in a computable algebraic model

Cites Work

• Unnamed Item
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• On the complexity of computations under varying sets of primitives
• Proving simultaneous positivity of linear forms
• On the Polyhedral Decision Problem