Hard definition

• Set of all languages that can be decided using a Deterministic TM in Polynomial time
• The class of efficiently decidable languages

Easier definition

Set of all problems that can be solved using a deterministic algorithm with Polynomial time complexity (computed using Asymptotic Notation)

Class FP

• The same concept, for functions that can return anything (not just a single boolean)
• All problems in P are obviously in FP
• Problems in FP are NOT necessarily in P

How Prove

How to prove a problem is in P

Either:

• Create a TM that solves the problem in polynomial number of steps in regard to length of input string
• Write a pseudocode and express 4 things:
  1. Input can be converted to binary using Binary encoding
  2. Total number of executed instructions are Polynomial
  3. All intermediate results have Polynomial size (VERY IMPORTANT)
  4. All instructions take Polynomial time to run

How to prove a problem is NOT in P

You can't