בעיית ספירה

בתחום תורת הסיבוכיות החישובית ותורת החישוביות, בעיית ספירה היא סוג של בעיה חישובית. אם R היא בעיית חיפוש אזי

היא פונקציית ספירה מתאימה, ו־ מסמנת את בעיית ההכרעה המתאימה.

יש לשים לב כי cR היא בעיית חיפוש בעוד ש־R# היא בעיית הכרעה. עם זאת, ניתן להפחית בקוק (Cook-reduction) את cR ל־R# (עבור C מתאים) באמצעות חיפוש בינארי. הסיבה לכך ש־R# מוגדרת בדרך זו, ולא כגרף של cR, היא כדי לאפשר את ביצוע החיפוש הבינארי.  

 מחלקת סיבוכיות ספירה 
בדומה לכך של־NP קיימות בעיות NP-שלם באמצעות הפחתה many-one, כך גם ל־P# קיימות בעיות P#-שלם באמצעות הפחתה שימורית (parsimonious reductions), כלומר טרנספורמציות בעיות השומרות על מספר הפתרונות.

 ראו גם 

 מדעי המחשב
 בעיית העצירה

 קישורים חיצוניים 

הערות שוליים

קטגוריה:בעיות חישוביות