Conceptually a decision problem is

Conceptually a decision problem is a problem that takes as input some string w over an alphabet Σ, and outputs "yes" or "no". If there is an algorithm (say a Turing machine, or a computer program with unbounded memory) that can produce the correct answer for any input string of length n in at most cnk steps, where k and c are constants independent of the input string, then we say that the problem can be solved in polynomial time and we place it in the class P. Formally, P is defined as the set of all languages that can be decided by a deterministic polynomial-time Turing machine. That is,


where


and a deterministic polynomial-time Turing machine is a deterministic Turing machine M that satisfies the following two conditions:

M halts on all input w and
there exists such that , where O refers to the big O notation and

ผลลัพธ์ (ไทย) 1:

ทางแนวคิดตัดสินปัญหาเป็นปัญหาที่ใช้เป็นอินพุตสายบาง w Σตัวอักษร และแสดงผลที่ "ใช่" หรือ "ไม่" ถ้าไม่มีอัลกอริทึม (กล่าวว่าเครื่องจักรทัวริง หรือโปรแกรมคอมพิวเตอร์ที่ มีหน่วยความจำงที่) ที่สามารถให้คำตอบที่ถูกต้องสำหรับสายอักขระใด ๆ เข้า n ความยาวมากที่สุด cnk ขั้นตอน ที่ k และ c เป็นค่าคงที่ขึ้นอยู่กับสายสัญญาณ ที่เราบอกว่า ปัญหานี้สามารถแก้ไขได้ในเวลาโพลิโนเมีย และเราทำในคลาส P. อย่างเป็นกิจจะลักษณะ, P ถูกกำหนดเป็นชุดของภาษาทั้งหมดที่สามารถตัดสินใจ โดยเครื่องจักรทัวริงพหุนามเวลา deterministic นั่นก็คือซึ่งและเครื่องจักรทัวริงพหุนามเวลา deterministic เป็น deterministic ทัวริงเครื่อง M ที่ตรงตามเงื่อนไขสองเงื่อนไขต่อไปนี้:M หยุดบนทั้งหมดเข้าวัตต์ และมีที่ ที่ O หมายถึงสัญกรณ์โอใหญ่ และ

ผลลัพธ์ (ไทย) 2:

แนวคิดการตัดสินใจปัญหาเป็นปัญหาที่ต้องใช้เวลาเป็น input สตริงบางกกว่าΣอักษรและเอาท์พุท "ใช่" หรือ "ไม่ใช่" หากมีอัลกอริทึม (พูดเครื่องทัวริงหรือโปรแกรมคอมพิวเตอร์ที่มีหน่วยความจำมากมาย) ที่สามารถผลิตเป็นคำตอบที่ถูกต้องสำหรับสตริงป้อนข้อมูลใด ๆ ของความยาว n ในขั้นตอนที่ cnk ที่มากที่สุดที่ k และ C เป็นค่าคงที่เป็นอิสระจากสายป้อน, แล้วเราบอกว่าปัญหาที่เกิดขึ้นสามารถแก้ไขได้ในเวลาพหุนามและเราวางไว้ในชั้นเรียนพีอย่างเป็นทางการ P ถูกกำหนดให้เป็นชุดของทุกภาษาที่สามารถตัดสินใจโดยพหุนามเวลาเครื่องทัวริงที่กำหนด นั่นคือที่และเวลาพหุนามเครื่องทัวริงกำหนดเป็นเครื่องทัวริงกำหนด M ที่สอดคล้องกับเงื่อนไขสองประการดังนี้: M หยุดกับการป้อนข้อมูลกว้างและมีอยู่เช่นว่าที่ O หมายถึงโน้ต O ขนาดใหญ่และ

ผลลัพธ์ (ไทย) 3:

ปัจจัยการตัดสินใจปัญหาเป็นปัญหาที่ใช้ป้อนข้อมูลสตริงตัวอักษร W มากกว่าΣและแสดงผลที่ " ใช่ " หรือ " ไม่ใช่ " ถ้ามีอัลกอริทึม ( พูดเครื่องจักรทัวริงหรือโปรแกรมคอมพิวเตอร์หน่วยความจำไม่จำกัด ) ที่สามารถผลิตคำตอบที่ถูกต้องสำหรับสัญญาณใด ๆของความยาวสตริงในที่ขั้นตอน cnk ส่วนใหญ่ ที่ K และ C เป็นค่าคงที่ที่เป็นอิสระของข้อมูลสตริงเรากล่าวว่า ปัญหาจะสามารถแก้ไขได้ในเวลาพหุนามและเราวางในชั้นหน้าอย่างเป็นทางการ , P หมายถึงชุดของภาษาทั้งหมดที่สามารถตัดสินใจโดยพหุนามเวลาเครื่องจักรทัวริงเชิงกำหนด . นั่นคือที่ไหน





และ deterministic พหุนามเวลาเครื่องจักรทัวริงเป็น deterministic เครื่องจักรทัวริง m ที่ตรงตามสภาพ

m
w และหยุดพักเข้าทั้งหมดมีอยู่ที่ที่โออ้างถึงสัญกรณ์โอใหญ่และ