วิทยานิพนธ์ของ Cobhamหรือที่รู้จักกันในชื่อวิทยานิพนธ์ Cobham–Edmonds (ตั้งชื่อตามAlan CobhamและJack Edmonds ) ^{[ 1 ] [ 2 ] [ 3 ]}ยืนยันว่าปัญหาการคำนวณสามารถคำนวณได้อย่างเป็นไปได้บนอุปกรณ์การคำนวณบางอย่างก็ต่อเมื่อสามารถคำนวณได้ในเวลาพหุนามนั่นคือ ถ้าปัญหานั้นอยู่ในระดับความซับซ้อนP [ ^{4 ] ในแง่สมัยใหม่ วิทยานิพนธ์}นี้ระบุปัญหาที่จัดการได้ซึ่งอยู่ในระดับความซับซ้อนP

ในเชิงทฤษฎี การกล่าวว่าปัญหาหนึ่งสามารถแก้ไขได้ในเวลาพหุนาม หมายความว่ามีอัลกอริทึมที่เมื่อรับข้อมูลปัญหาขนาดn บิตเป็นอินพุต สามารถสร้างคำตอบได้ในเวลา O( nc ) โดยใช้สัญกรณ์บิ๊กโอและcเป็นค่าคงที่ที่ขึ้นอยู่กับปัญหา แต่ไม่ขึ้นอยู่กับข้อมูลปัญหาเฉพาะเจาะจง^นั้น

บทความของ Alan Cobham ในปี 1965 ที่มีชื่อว่า "ความยากลำบากในการคำนวณโดยเนื้อแท้ของฟังก์ชัน" ^{[ 5 ]}เป็นหนึ่งในการกล่าวถึงแนวคิดของคลาสความซับซ้อนP เป็นครั้งแรก ซึ่งประกอบด้วยปัญหาที่สามารถตัดสินได้ในเวลาพหุนาม Cobham ตั้งทฤษฎีว่าคลาสความซับซ้อนนี้เป็นวิธีที่ดีในการอธิบายชุดของปัญหา ที่สามารถ คำนวณ ได้

บทความ "Paths, trees, and flowers" ของ Jack Edmonds ในปี 1965 ^{[ 6 ]}ยังได้รับการยกย่องว่าระบุPด้วยปัญหาที่สามารถแก้ไขได้^{[ 7 ]}

แม้ว่าวิทยานิพนธ์ของคอบแฮมจะเป็นก้าวสำคัญในการพัฒนาทฤษฎีความซับซ้อนของการคำนวณแต่ก็มีข้อจำกัดเมื่อนำไปใช้กับความเป็นไปได้ในทางปฏิบัติของอัลกอริทึม วิทยานิพนธ์นี้กล่าวโดยพื้นฐานว่า " P " หมายถึง "ง่าย เร็ว และใช้งานได้จริง" ในขณะที่ "ไม่อยู่ในP " หมายถึง "ยาก ช้า และใช้งานไม่ได้จริง" แต่สิ่งนี้ไม่เป็นความจริงเสมอไป เพราะวิทยานิพนธ์นี้ละเลยตัวแปรสำคัญบางอย่างที่ส่งผลต่อเวลาในการทำงานในทางปฏิบัติ:

• มันไม่สนใจค่าคงที่และพจน์ลำดับต่ำกว่า
• มันไม่สนใจขนาดของเลขชี้กำลังทฤษฎีบทลำดับชั้นเวลาพิสูจน์การมีอยู่ของปัญหาในPที่ต้องการเลขชี้กำลังขนาดใหญ่ตามอำเภอใจ
• มันไม่คำนึงถึงขนาดโดยทั่วไปของข้อมูลที่ป้อนเข้ามา

ทั้งสามข้อมีความเกี่ยวข้องกันและเป็นข้อร้องเรียนทั่วไปเกี่ยวกับการวิเคราะห์อัลกอริทึมแต่โดยเฉพาะอย่างยิ่งจะใช้ได้กับวิทยานิพนธ์ของ Cobham เนื่องจากมีการอ้างอย่างชัดเจนเกี่ยวกับความสามารถในการใช้งาน ภายใต้วิทยานิพนธ์ของ Cobham ปัญหาที่อัลกอริทึมที่ดีที่สุดใช้ คำสั่ง n ²⁰⁰ถือว่าสามารถแก้ไขได้ และปัญหาที่มีอัลกอริทึมที่ใช้คำสั่ง 2 ^{0.00001 n} ถือว่าไม่สามารถแก้ไขได้ —แม้ว่าจะไม่สามารถแก้ปัญหาที่มีขนาดn  =  2 ด้วยอัลกอริทึมแรกได้ ในขณะที่ปัญหาที่มีขนาดn  =  10 ⁶สามารถแก้ไขได้โดยไม่มีปัญหา ในสาขาที่ปัญหาในทางปฏิบัติมีตัวแปรนับล้าน (เช่นการวิจัยการดำเนินงานหรือการออกแบบระบบอิเล็กทรอนิกส์อัตโนมัติ ) แม้แต่อัลกอริทึม O( n ³ ) ก็มักจะใช้งานไม่ได้^{[ 9 ]}

อีกประเด็นที่ควรพิจารณาคือ ในหลายกรณี เรามักจะพอใจกับ คำตอบ โดยประมาณหากไม่สามารถหาคำตอบที่แน่นอนได้ ตัวอย่างเช่นปัญหาพนักงานขายเดินทาง (Travelling Salesman Problem ) เป็นที่เชื่อกันอย่างกว้างขวางว่าไม่สามารถหาคำตอบที่แน่นอนได้ในเวลาพหุนาม (เป็นปัญหาNP-hard ) แต่สามารถหาคำตอบที่ดีได้ในเวลาพหุนามด้วยวิธีการต่างๆ เช่น อัลกอริทึมของคริสโตฟิเดส (Christofides algorithm )