New answers tagged

18

FOR x := 1 TO n DO FOR y := 1 TO n DO FOR z := 1 TO n DO IF E(x,y) && E(y,z) && E(z,x) THEN REJECT ACCEPT Each of the variables x, y and z requires $\Theta(\log \texttt{n})$ bits to store an integer between $1$ and $\texttt{n}$.


15

You don't need to first write all 3-tuples and then check, for each of them, whether it induces a triangle. You can just enumerate the 3-tuples one at a time and reject as soon as you find one that induces a triangle. If you reach past the last 3-tuple then the graph contains no triangle and you can accept.


2

Given an integer k, are there integers (positive or negative) x, y, z with an absolute value ≤ $10^{1000}$ such that $x^3 + y^3 + z^3 = k$? It is believed that without the limit on the absolute values the answer is "Yes" unless $k \equiv 4 \mod 9$ or $k \equiv 5 \mod 9$. On the other hand, solutions are so rare that most likely solutions for some values k ...


1

If you consider space and time limitation, it'll be safe to assume that almost every Decidable problem (as per the exact definition) can have version that can be computationally not solvable. That said, Turing machines are not a practical model for computing. Even in the theoretical computer science community, the more realistic RAM machines are used ...


Top 50 recent answers are included