On the complexity of computations under varying sets of primitives

DOI10.1016/0022-0000(79)90054-0zbMath0409.68023OpenAlexW2050394746MaRDI QIDQ1259164

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(79)90054-0

zbMATH Keywords

Computational Complexity Generalized Hyperplane N-Dimensional Knapsack Problem Search Problem Search Programm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Search theory (90B40) Discrete mathematics in relation to computer science (68R99)

Related Items

Legal coloring of graphs ⋮ Scattered Factor-Universality of Words ⋮ Geometric complexity of some location problems ⋮ Lower bound arguments with ``inaccessible numbers ⋮ Lower bounds for arithmetic networks. II: Sum of Betti numbers ⋮ ON-LINE SEAT RESERVATIONS VIA OFF-LINE SEATING ARRANGEMENTS ⋮ Establishing order in planar subdivisions ⋮ Rough analysis of computation trees ⋮ A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model ⋮ Absent Subsequences in Words ⋮ On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination ⋮ Time and space complexity of deterministic and nondeterministic decision trees ⋮ Linear-time construction of two-dimensional suffix trees ⋮ A parallel algorithm for channel routing ⋮ Linear decision trees are too weak for convex hull problem ⋮ Finding connected components of an intersection graph of squares in the Euclidean plane ⋮ Comparisons between linear functions can help ⋮ Proximity problems for points on a rectilinear plane with rectangular obstacles ⋮ An optimal algorithm for the minimum disc cover problem ⋮ On topological lower bounds for algebraic computation trees ⋮ A note on a \(P \neq NP\) result for a restricted class of real machines ⋮ Lower bounds for sorting of sums ⋮ On digital nondeterminism ⋮ Worst-case versus average case complexity of ray-shooting ⋮ 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 ⋮ Some speed-ups and speed limits for real algebraic geometry ⋮ On constant factors in comparison-based geometric algorithms and data structures ⋮ Lower bounds on probabilistic linear decision trees ⋮ Bounds for the Element Distinctness Problem on one-tape Turing machines ⋮ THE OBJECT COMPLEXITY MODEL FOR HIDDEN-SURFACE REMOVAL ⋮ Some dynamic computational geometry problems

Cites Work