tag:blogger.com,1999:blog-3722233.post5655789602676044507..comments2022-11-23T12:43:47.064-06:00Comments on Computational Complexity: Are there any natural problems complete for NP INTER TALLY? NP INTER SPARSE?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-43324142218038585442019-09-26T03:22:01.829-05:002019-09-26T03:22:01.829-05:00A small note on "natural"; what is $1^a$...A small note on "natural"; what is $1^a$ ... it's a number (a) in unary encoding.<br /><br />So we are asking for "natural" problems that have a single number (represented inefficiently) as input ...<br /><br />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.<br /><br />We have FACTORING but no other come to my mind ...<br /><br />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.<br /><br />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.<br /> <br />In binary representation, N^3 "contains" the famous natural NPC problem QUADRATIC DIOPHANTINE EQUATION (as long as a math problem can be considered natural :-). <br /><br />But with TALLY^3 it seems that you can't do too much.<br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br />Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.com