Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons

&
Mathematical Logic Quarterly 41 (2):261-267 (1995)
  Copy   BIBTEX

Abstract

D. T. Lee and A. K. Lin [2] proved that VERTEX-GUARDING and POINT-GUARDING are NP-hard for simple polygons. We prove that those problems are NP-hard for ortho-polygons, too

Categories

Keywords

Reprint years

DOI

10.1002/malq.19950410212

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Variants of Visibility and their Complexity.Dietmar Schuchardt & Hans-Dietrich Hecker - 1998 - Mathematical Logic Quarterly 44 (4):522-528.
Hard-core extensionalism and the analysis of belief.Don Brownstein - 1982 - Noûs 16 (4):543-566.
Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.F. Stephan & B. Borchert - 2000 - Mathematical Logic Quarterly 46 (4):489-504.
Analysing Sellars.Stathos Psillos - unknown
Simple truths, hard problems: Some thoughts on terror, justice, and self-defence.Noam Chomsky - 2005 - Philosophy 80 (1):5-28.
A Phenomenological Reading of Hegel’s Concept of History of Philosophy: An Analysis of “The Gallery of Opinions”, “The Gallery of Knowledge” and “The Gallery of Dresden”.Ke Xiaogang - 2005 - Frontiers of Philosophy in China 1 (1):51-59.
Explaining the mind: Problems, problems.Stevan Harnad - 2001 - The Sciences 41 (2):36-42.
There is no hard problem of consciousness.Kieron O'Hara & Tom Scutt - 1996 - Journal of Consciousness Studies 3 (4):290-302.
To appraise developmental difficulty or mental demand, relational complexity is not enough.Juan Pascual-Leone - 1998 - Behavioral and Brain Sciences 21 (6):843-844.
Generic Complexity of Undecidable Problems.Alexei G. Myasnikov & Alexander N. Rybalov - 2008 - Journal of Symbolic Logic 73 (2):656 - 673.
Some decision problems of enormous complexity.Harvey Friedman - manuscript
Analog vs. digital computation.David J. Chalmers - manuscript

Analytics

Added to PP
2013-12-01

Downloads
21 (#715,461)

6 months
5 (#652,053)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references