> some clarification to show that this is a friendly discussion :) Thanks, people assume the worst intentions because of the lack of tone in written messages.

> some clarification to show that this is a friendly discussion :) Thanks, people assume the worst intentions because of the lack of tone in written messages. :-) > You essentially say that the predicate only exists once it has been created, but I say it has merely been given a name to reference it. I don't see how this distinction makes much of a difference. Does a predicate exist if no human is thinking about it? Before anyone defined the problem for the first time, the problem didn't exist and therefore it couldn't have properties. Unless I was salesperson with a singularly mathematical mind, I would not try to solve the problem for every possible case but just for the particular set of cities that I traveled through. And if I happened to be a rural Chinese, [1] ;-) I may well be able to solve my problem in polynomial time. NP-completeness is a property of a family of problem instances, so it matters only when you are studying the whole family, even though it may affect any particular instance (or not). [1] i.e., there may be subsets of the general problem that may be solved in polynomial time, and my particular instance may belong to that subset. See Rural postman problem and Chinese postman problem https://kups.ub.uni-koeln.de/54671/1/rep-92.113-koeln.pdf https://kups.ub.uni-koeln.de/54671/1/rep-92.113-koeln.pdf https://en.wikipedia.org/wiki/Chinese_postman_problem https://en.wikipedia.org/wiki/Chinese_postman_problem However, let's assume that we have defined the problem in its general terms. So, does the property of being a hard problem exist as soon as you state it, as an inescapable consequence of its formal definition, even before someone starts to study its complexity? I'd say absolutely yes, and if that's what you mean saying that the property 'exists', then we are on the same page. > Maybe you can come up with a formal proof why a predicate can only exist once it has been formalized for the first time? Yest, I think I could do that if I tried. I also think that I could do the opposite if I tried, showing that any predicate exists from the start of time, just waiting to be discovered. You see, the problem with formalism is that the theorems that can be proven depend completely on the assumptions you incorporate when defining a specific formal system; therefore, I can orient the reasoning towards one conclusion or the other as I am interested, as long as it does not incorporate a set of axioms and rules of inference that produce an internal contradiction. Formal systems are most valuable because they allow us to get rid of inconsistent assumptions in our reasoning, not necessarily because those statements correspond exactly one-to-one to entities in the real world.