How to determine computational infeasibility of NP Complete

Question

For an NP complete problem, how is computational infeasibility determined?

Are there guidelines that that determine whether an NP Complete problem is computationally infeasible?

Answer 1

For an NP complete problem, how is computational infeasibility determined?

Short answer: it isn't.

Since "P versus NP" is still an unsolved problem, we don't know if there is an efficient (=polynomial time) algorithm for solving any of those NP complete problems. It is just a fact that noone has discovered such an algorithm so far, though it may be possible that one exists (and if a polynomial time algorithm for one of those NP complete problems were known, all of them would be solvable in polynomial time).

Moreoever, you did not tell us what you mean by the colloquial term "computational infeasibility". NP complete problems can be (at least in theory) solved very well by a computer, so all of them are literally "computational feasible". We just don't know an efficient algorithm for them, which makes it practically infeasible to solve most NP complete problems for "relatively small input sizes" in the limited amount of time we have available where a solution would be useful for someone.

Are there guidelines that that determine whether an NP complete problem is computationally infeasible?

Even if you mean "computationally infeasible" in the sense that there is no efficient algorithm known for them, this question makes not much sense - any NP complete problem is currently computationally infeasible in this sense. If you mean how to determine if a problem is NP complete: this is usually done by showing that a new problem is equivalent to an existing problem which is already know to be NP-complete.