Infinite versions of some NP-complete problems

Details Infinite versions of some NP-complete problems Infinite versions of some NP-complete problems

1995-03-10

arxiv.org/abs/math/9503205v1

Mathematics

Logic

Scientific paper

Recently, connections have been explored between the complexity of finite problems in graph theory and the complexity of their infinite counterparts. As is shown in our paper (and in independent work of Tirza Hirst and D. Harel from a different angle) there is no firm connection between these complexities, namely finite problems of equal complexity can have radically different complexity for the infinite versions and vice versa. Furthermore, the complexity of an infinite counterpart can depend heavily on precisely how the finite problem is rephrased in the infinite case. The finite problems we address include colorability of graphs and existence of subgraph isomorphisms. In particular, we give three infinite versions of the 3-colorability problem that vary considerably in their recursion theoretic and proof theoretic complexity. Additionally, we show that three subgraph isomorphism problems of varying finite complexity have infinite versions with identical recursion theoretic and proof theoretic content.

Affiliated with

Also associated with

No associations

Rating

Infinite versions of some NP-complete problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Infinite versions of some NP-complete problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infinite versions of some NP-complete problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-296876