go-v.orgdoi

On the Polyhedral Decision Problem

Andrew Chi-Chih Yao, Ronald L. Rivest · SIAM Journal on Computing · 1980

  • DOI 10.1137/0209028
  • Publisher Society for Industrial and Applied Mathematics
  • Type article
  • Issued 1980

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

SIAM Journal on Computing · Society for Industrial and Applied Mathematics · article · 1980

Abstract

Computational problems sometimes can be cast in the following form: Given a point ${\bf x}$ in $R^n $, determine if ${\bf x}$ lies in some fixed polyhedron. In this paper we give a general lower bound to the complexity of such problems, showing that $\frac{1}{2}\log _2 f_s $ linear comparisons are needed in the worst case, for any polyhedron with $f_s$s-dimensional faces. For polyhedra with abundant faces, this leads to lower bounds nonlinear in n, the number of variables.

Open the resolved locator · 10.1137/0209028

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 05:09 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1137/0209028
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.