Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
From MaRDI portal
Publication:1050255
DOI10.1007/BF02218439zbMath0512.90076OpenAlexW1975384529MaRDI QIDQ1050255
Publication date: 1983
Published in: BIT (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02218439
exponential lower boundsNP-completeness23, 181-192 (1983)linear recognition problemlinear test functionslower bounds on the number of comparisonsrestricted linear decision tree modelternary comparisons
Related Items
Lower bound arguments with ``inaccessible numbers, Lower bounds for sorting of sums, Stability versus speed in a computable algebraic model
Cites Work