An NP-Complete Problem Arising from a Brute Force Search for Limits of Subsets of B n

Authors

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

Keywords:

NP-Complete, limits, binary vector spaces, computational complexity

Abstract

A brute force search for limites of a subset of Bn = (0,1 Jn 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

1998-12-31

Issue

Vol. 4 No. 3/4 December (1998)

Section

Independent Refereed Articles