0

If $f$ is a function $\mathbb N\to\{\text{True},\text{False}\}$, then I know what it means to say that $f$ is in NP. But if $f$ is a function $A\to \{\text{True},\text{False}\}$, where $A$ is a set, then I do not know what that means.

The Boolean satisfiability problem (SAT) is known to be in NP, but what exactly does that mean? The domain $A$ of SAT is the set of all propositional-logic-formulas. Have people agreed to use some specific function $A\to\mathbb N$ as an encoding?

zxcv
  • 1,445
  • https://en.wikipedia.org/wiki/NP_(complexity) "NP (nondeterministic polynomial time) is a complexity class used to classify decision problems" https://en.wikipedia.org/wiki/Decision_problem "a decision problem is a computational problem that can be posed as a yes–no question of the input values". So no, functions $\mathbb N \to \mathbb N$ are not in NP. – Dmitry Dec 08 '23 at 06:16
  • @Dmitry I think I should change $\mathbb N\to\mathbb N$ to $\mathbb N\to{\text{True},\text{False}}$. I will edit my question. – zxcv Dec 08 '23 at 06:20
  • It doesn't matter what encoding one uses as long as it can be decoded in polynomial time, and it's quite easy to come up with one that can be decoded in linear time. – MJD Dec 08 '23 at 06:30
  • @MJD I only know the definition of P class for functions $\mathbb N\to\mathbb N$. So I do not know what "A function $A\to\mathbb N$ can be decoded in polynomial time" means. – zxcv Dec 08 '23 at 06:41

1 Answers1

1

In fact your premise is mistaken. Complexity classes like P, NP, and NPC are defined for decision problems on sets of strings, not sets of numbers. (Sets of strings are called “languages” in the jargon.)

The concept can easily be extended to sets of numbers because numbers can be encoded as strings. For example the number $119$ can be encoded as the string 119 or as 1110111.

Similarly formulas are easily encoded as strings. For example the formula $(a\land b)\lor(\lnot a\land c)$ can be encoded as the string (a∧b)∨(¬a∧c).

The exact details of the encoding we choose are not really important, as long as the length of the string is.polynomial in the “size” of the problem. Sometimes this is important but usually we can ignore the details.

The Garey and Johnson book has a more detailed discussion of this point, but they will tell you the same thing. Encoding formulas or graphs as strings is no different in principle than encoding numbers as strings.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • 1
    In this question I discussed the same issue in connection with decidable sets of numbers and decidable sets of strings. The two notions are essentially the same because numbers can be encoded as strings and an algorithm can decode the string to find the number it represents. – MJD Dec 08 '23 at 06:59
  • Since the set of all alphabets should be finite, we cannot have $\Sigma={\land,\lor,\neg,x_0,x_1,x_2,\ldots}$ as the set of all alphabets. So there should be an encoding $\Sigma^\to{0,1}^$. Is it right that any encoding that a "reasonable" person would do makes the problem NP, although there is no formal definition of the time-complexity of encodings? – zxcv Dec 08 '23 at 09:46
  • You're right about the problem.with the variables. It's easy to fix. Think about it a little. You will find a solution. – MJD Dec 08 '23 at 13:27
  • We don't need to define time-complexity of an encoding because the algorithm never "decodes" anything, it just reads the input string and decides if the string is in the set. And the time complexity of making the decision is defined in terms of the length of the input string. You know that P is the class of languages that can be decided in polynomial time. But a polynomial is a function. What is this a polynomial function of? P is the class of languages that can be decided in a time that is a polynomial function of the length of the input string. – MJD Dec 08 '23 at 13:29
  • 2
    You should read the Garey and Johnson book instead of whatever you were reading before. It will clear all this up for you. – MJD Dec 08 '23 at 13:49
  • I read the book and it became clear to me. Thanks. – zxcv Dec 14 '23 at 01:16
  • I'm glad I could help. – MJD Dec 14 '23 at 03:22
  • Did you figure out a way to fix the problem of encoding an infinite family of variables with a finite alphabet? – MJD Dec 14 '23 at 03:34
  • I was thinking of encoding $x_0\mapsto0$, $x_1\mapsto1$, $x_2\mapsto00$, $x_3\mapsto10$, $x_4\mapsto01$, $x_5\mapsto11$, $x_6\mapsto000$, etc. But before I read the book, I did not know how one could tell whether this is a reasonable encoding, although it does seem reasonable. What was your answer anyway? – zxcv Dec 15 '23 at 02:46