How is it possible to prove that this assert is not true?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Regarding to Popper's Falsifiability theory you can falsify this proposal by this assertion:
It is false if (and only if) to find (giving the result) each Hamilton Path in at least one Complete Euclidean Graph, for every possible algorithm has a cost greater than a polynomial expression of the number of items.
$\begingroup$
$\endgroup$
5
This assertion is, in fact, true. A complete graph (which doesn't even have to be Euclidean) always has a Hamiltonian path: number the vertices in an arbitrary order, start at the first one, then proceed in order to the last (and then back to the first to make a cycle if you want). Since the graph is complete, the edges you need will always exist.
Thus, the problem can be decided in $O(1)$, which is polynomial, so it is in $P$. The algorithm is trivial:
define doesThisCompleteGraphHaveAHamiltonianPath(G):
return Yes
-
$\begingroup$ Draconis, the question is about "how" to disprove this statement. I mean a formula that if it is true, then this statement would be false. $\endgroup$– IxerCommented Aug 31, 2018 at 17:22
-
1$\begingroup$ @Ixer What I'm saying is, it's impossible to disprove the statement, because the statement is provably true. $\endgroup$– DraconisCommented Aug 31, 2018 at 18:40
-
$\begingroup$ Thx @Draconis, it is about Popper´s method ... If someone find a counter-example (an special case) that disproves this assert, we have to think it is false ... I don´t agree at all with that. $\endgroup$– IxerCommented Aug 31, 2018 at 19:21
-
$\begingroup$ @Ixer Sorry, I don't really understand what you're saying. If a statement is proven true, and that proof is valid, then also proving the statement false would mean the underlying system of mathematics is inconsistent, and mathematical proofs in that system become utterly meaningless (look up the "principle of explosion"). $\endgroup$– DraconisCommented Aug 31, 2018 at 19:30
-
$\begingroup$ may be ... Some proofs makes me doubt of. I will take a look to the "principle of explosion". $\endgroup$– IxerCommented Aug 31, 2018 at 19:54