New answers tagged

1 vote

Is « Does exist at least one function $u$ such that $f(u(0)) \ne g(u(0))$? » an NP problem? or a P problem?

I'm going to assume that $f:A\to B$ and $g:A\to B$ for some (known) sets $A$ and $B$ and that, given a set $C\ni0$ we are to find a function $u:C\to A$ such that $f(u(0))=g(u(0))$. Of course, this is ...
Charles's user avatar
  • 256
0 votes

Subset sum reducible to barter economy problem?

You can reduce from subset-sum as follows: given a set of $n$ positive integers $x_1, \dots, x_n$ and a positive integer target $T$, consider an instance with $2$ people $p_1, p_n$ and $n+1$ objects $...
Steven's user avatar
  • 28.2k
1 vote

If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?

Languages are a good way of discussing yes or no questions with a finite bit-length input size. There are plenty of alternatives to languages, in complexity theory! They often have some 'moral ...
Alex Meiburg's user avatar

Top 50 recent answers are included