I can reduce 3-Sat to the following NP-Complete decision problem:

Let $S = ${0,1,...,s-1}, $D \subseteq S$ and $P$ be a multivariate polynomial in $n$ variables. Decide yes iff there exists $\vec x \in D^{n}$ such that $P(\vec x) \neq 0 (mod \ s)$.

That got me thinking that I can make the problem seem much harder by rephrasing the problem as:

Let $\mathbb{F}$ be a field, $f$ be some function over $\mathbb{F}$ and $D$ be a restriction of the domain of $\mathbb{F}$. Decide yes iff there exists $x \in D$ such that $f(x) \neq 0$.

With this new problem, I don't know the size of the inputs. If I restrict myself to polynomials and modular arithmetic, the functions can only admit operations done in polynomial time, so their "sizes" seem obvious. How can I talk about the time complexity of deciding or verifying that a function is not identically 0? e.g. $sin(1) \neq 0$ in $\mathbb{R}$


1 Answer 1


You can't. First, you have to specify the problem in a precise way, before it is meaningful to talk about its time complexity. If you are not sure how to formulate the problem exactly, then you can't talk about its time complexity yet.

Part of the problem statement involves specifying how the inputs are represented.

Or, to put it in a more pedantic way, time complexity is associated with formal languages. A formal language $L$ is defined as a subset of $\{0,1\}^*$. So, to speak precisely, you first need to specify a well-defined language $L$; once you have done that, you can talk about its time complexity, but if you're not clear on what the language is, then it does not have a well-defined time complexity.

Often in informal speech, we talk in a more informal way, by describing a problem informally. This is usually OK because it is usually clear to someone knowledgeable in the field how to convert that informal problem statement into a precise definition of a formal language. In many cases, there is a natural way to represent the inputs in the problem statement in a reasonable way, and this yields a specification of a formal language.

But you have to be careful. Some kinds of mathematical objects don't necessarily have any concise representation, so the details of how they are represented make a big difference. In your example, it is not clear how to represent $f$. Or, one natural way to represent a function is as a truth table -- but this representation can be very large, so the resulting time complexity (as a function of the length of the input) might not capture what you really want to know about.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.