# True or false? Any finite problem is in P

Please explain to me if this is true or false. I had this in an exam, and I really need to know if I got this correct. I believe it is true because finite problems have finite solutions, which can be done in polynomial time.

• Are you talking about decision problems? Commented Nov 9, 2023 at 21:24
• What do you mean by finite problem? the one that can be defined in constant number of bits? Commented Nov 9, 2023 at 21:25

If by finite problem, you mean a problem with a finite domain, then yes. Such problems are not only in P, but can be done in constant time since you can build a mapping between every possible input and its correct output.

• I am not sure about constant time, since you would need to read the input to map to the answer correctly. Commented Nov 9, 2023 at 23:01
• @Nathaniel, If we are talking about finite languages, then reading roughly as much input as the length of the longest accepted word (i.e., a constant) suffices. Commented Nov 9, 2023 at 23:58
• @Steven You are right, of course! Commented Nov 10, 2023 at 5:55