Counting problem Definition and 58 Threads

In computational complexity theory and computability theory, a counting problem is a type of computational problem. If R is a search problem then





c

R


(
x
)
=
|
{
y

R
(
x
,
y
)
}
|



{\displaystyle c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,}
is the corresponding counting function and




#
R
=
{
(
x
,
y
)

y


c

R


(
x
)
}


{\displaystyle \#R=\{(x,y)\mid y\leq c_{R}(x)\}}
denotes the corresponding decision problem.
Note that cR is a search problem while #R is a decision problem, however cR can be C Cook-reduced to #R (for appropriate C) using a binary search (the reason #R is defined the way it is, rather than being the graph of cR, is to make this binary search possible).

View More On Wikipedia.org
  1. H

    Solve Counting Problem: How Many Students Left Unfinished?

    Homework Statement There are 285 math students. First homework was completed by 166 students, second by 148 and third by 129. First and second was completed by 108 students, first and third by 83 and second and third by 25 students. How many students have not completed at least one homework...
  2. M

    Counting Problem: How to Get the Right Answer?

    Suppose you pick a k-element subset of {1, 2, ..., n}, call it A. How many of the other k-element subsets have k-1 elements in common with A? I've been at this for quite some time, but I always overcount. Can anyone help me out? My last attempt gave me (n-k+1)k - \frac{k(k-1)}{2}, which isn't...
  3. M

    Counting problem, exactly 5 heads obtained, coin

    Hello everyone, I'm having some issues on this problem: A coin is tossed ten times. In each case the outcome H (for heads) or T (for tails) is recorded. (One possible outcome of the ten tossings is denoted THHTTTHTTH.) I got a, d right i believe. but I need someone to check if i did the...
  4. L

    Solving 5-Stone Counting Problem w/ Restrictions

    Hi, I wasn't sure how to approach this problem: You have 5 differently colored stones-red, orange, blue, green, purple. If the green stone cannot be placed at the front or the back of the sequence, how many possible arrangements can you make? I know that without the above restriction, the...
  5. A

    How Many 3-Letter Arrangements of aabbcccdddd Are Possible?

    hi everyone... how many arrangements of this word "aabbcccdddd" is possible if we only use 3 of them? I know if we could use all of them it would just be 11!/(2!2!3!4!), but what if we only use 3? :confused: Thanks in advance
  6. F

    Counting Problem: Proving the Integer Property of ((n^2)!)!/(n!)^(n+1)

    show that \frac{ ((n^2)!)!}{(n!)^{n+1}} is an integer. i was thinking of saying that there are so many people who can be put on a committee, etc etc which would make an integer. i don't think this is real hard but nothing is really jumping out at me
  7. T

    How Many Subsets of a Set with Odd Elements Can Have Half or Fewer Elements?

    The question is... How many subsets of a (2n+1)-element set have n elements or less? To figure this out I started by using a workable example. Obviously n must be small to keep the total number of subsets small. So I started with n=1 and so there are 8 total subsets. And of course in...
  8. gimpy

    Distributing 5 Objects to 3 Boxes: C(5,3)

    I think i got this answer. How many ways are there to distribute five distinguishable objects into three indistinguishable boxes? Wouldn't the answer just be C(5,3) because the boxes are indistinguishable? Or do i treat this question the same as if the boxes were distinguishable?
Back
Top