Monday, September 09, 2019

Are there any natural problems complete for NP INTER TALLY? NP INTER SPARSE?


A is a tally set if A ⊆ 1*.

A is a sparse set if there is a polynomial p such that the number of strings of length n is ≤ p(n).

If there exists a sparse set A that is NP-hard under m-reductions (even btt-reductions) then P=NP. (See this post.)

If there exists a sparse set A that is NP-hard under T-reductions then PH collapses. (See this post.)

Okay then!

I have sometimes had a tally set or a sparse set that is in NP and I think that its not in P. I would like to prove, or at least conjecture, that it's NP-complete. But alas, I cannot since then P=NP. (Clarification: If my set is NP-complete then P=NP. I do not mean that the very act of conjecturing it would make P=NP. That would be an awesome superpower.)

So what to do?

A is NPSPARSE-complete if A is in NP, A is sparse, and for all B that are in NP and sparse, B ≤m A.

Similar for NPTALLY and one can also look at other types of reductions.

So, can I show that my set is NPSPARSE-complete? Are there any NPSPARSE-complete sets? Are there NATURAL ones? (Natural is a slippery notion- see this post by Lance.)

Here is what I was able to find out (if more is known then please leave comments with pointers.)

1) It was observed by Bhurman, Fenner, Fortnow, van Velkebeek that the following set is NPTALLY-complete:

Let M1, M2, ... be a standard list of NP-machines. Let

A = { 1(i,n,t) : Mi(1n) accepts on some path within t steps }'

The set involves Turing Machines so its not quite what I want.

2) Messner and Toran show that, under an unlikely assumption about proof systems there exists an NPSPARSE-complete set. The set involves Turing Machines. Plus it uses an unlikely assumption. Interesting, but not quite what I want.

3) Buhrman, Fenner, Fortnow, van Melkebeek also showed that there are relativized worlds where there are no NPSPARSE sets (this was their main result). Interesting but not quite what I want.

4) If A is NE-complete then the tally version: { 1x : x is in A } is likely NPTALLY-complete. This may help me get what I want.

Okay then!

Are there any other sets that are NPTALLY-complete. NPSPARSE-complete? The obnoxious answer is to take finite variants of A. What I really want a set of such problems so that we can proof other problems NPTALLY-complete or NPSPARSE-complete with the ease we now prove problems NP-complete.

No comments:

Post a Comment