Monday, September 09, 2019

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


Recall:

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.



at

1 comment:

  1. Marzio De Biasi3:22 AM, September 26, 2019

    A small note on "natural"; what is $1^a$ ... it's a number (a) in unary encoding.

    So we are asking for "natural" problems that have a single number (represented inefficiently) as input ...

    I think we also have serious problems to find natural problems (or NPC natural problems) that has a sigle number (represented efficiently) as input; i.e. problems that don't use that number as an encoding for something else.

    We have FACTORING but no other come to my mind ...

    Even COMPRESSIBILITY ("Is it N compressible?") is a kind of hack because it hides the fact that what we are really asking for is the compressibility of the 0-1 string that represents/is represented by N.

    Also note that TALLY could be extended to TALLY^k, i.e. a *fixed* number of unary strings (1^{a_1},..,1^{a_k}) and the corresponding hierarchy could be "investigated" ... I never seen it before but I think it could be interesting.

    In binary representation, N^3 "contains" the famous natural NPC problem QUADRATIC DIOPHANTINE EQUATION (as long as a math problem can be considered natural :-).

    But with TALLY^3 it seems that you can't do too much.












    ReplyDelete