New answers tagged decision-problem
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 ...
- 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 $...
- 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 ...
- 923
Top 50 recent answers are included