An NP-Complete Problem Arising From a Brute Force Search for Limits of Subsets of Bn

Authors

  • Keith B. Olson Montana Tech of the University of Montana, Butte, Montana

Keywords:

NP-Complete, limits, binary, vector spaces, complexity, brute force search

Abstract

A brute force search for limits of a subset of Bn = (0,1)n is shown to be NP-Complete. This is accomplished by demonstrating equivalence to an extension of the known NP-complete problem SATISFACTION. No results are postulated concerning sufficient conditions for the existence of such a limit.

Downloads

Published

2024-02-20

Issue

Vol. 4 No. 3/4 (1998)

Section

Biological Sciences - Terrestrial Ecosystems [Articles]