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 ...
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 $...
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 ...
Top 50 recent answers are included
Related Tags
decision-problem × 529complexity-theory × 177
np-complete × 136
np × 87
turing-machines × 71
computability × 68
algorithms × 65
reductions × 63
np-hard × 61
undecidability × 55
optimization × 26
time-complexity × 24
graphs × 23
satisfiability × 22
formal-languages × 17
polynomial-time × 17
p-vs-np × 16
complexity-classes × 15
halting-problem × 15
regular-languages × 14
semi-decidability × 14
search-problem × 14
context-free × 13
finite-automata × 12
terminology × 12