Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
type: Item
instance of: scholarly article
title: Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
zbMATH Open document ID: 0512.90076
DOI: 10.1007/BF02218439
author: Esko Ukkonen
published in: BIT
publication date: 1983-01-01T00:00:00Z
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3809332
zbMATH Keywords: 23, 181-192 (1983)
zbMATH Keywords: exponential lower bounds
zbMATH Keywords: restricted linear decision tree model
zbMATH Keywords: linear recognition problem
zbMATH Keywords: ternary comparisons
zbMATH Keywords: lower bounds on the number of comparisons
zbMATH Keywords: linear test functions
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
cites work: A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
cites work: On the complexity of computations under varying sets of primitives
cites work: Proving simultaneous positivity of linear forms
cites work: Q3926036
cites work: On the Polyhedral Decision Problem
full work available at URL: https://doi.org/10.1007/bf02218439
OpenAlex ID: W1975384529
description: scientific article; zbMATH DE number 3809332