Skip to main content
Marcos Villagra's user avatar
Marcos Villagra's user avatar
Marcos Villagra's user avatar
Marcos Villagra
  • Member for 14 years, 5 months
  • Last seen more than 11 years ago
comment
Aren't "oracle machines" unsound concepts?
Yes, but to my knowledge in complexity only decidable languages are used as oracles.
revised
Aren't "oracle machines" unsound concepts?
added 7 characters in body
Loading…
awarded
revised
Aren't "oracle machines" unsound concepts?
edited body; added 209 characters in body
Loading…
comment
Aren't "oracle machines" unsound concepts?
I forgot to mention that oracles need to be a decidable language. And to answer your question consider a P machine M (machine with polynomially-bounded resources) with an oracle to another P machine N. Then $L(M^N) \in P$, and in general $P^O=P$ for any given $O$. So here there is no contradiction.
answered
Loading…
comment
Number of subset sums
that number is not necessarily a natural, because it is a ratio like approximate number of solutions per random $D$. Maybe you can take the floor or ceiling of that.
awarded
comment
Number of subset sums
What I mean is how many summations with $k$ terms equals $s$? So $k$ is fixed, and clearly $k < n$.
accepted
awarded
asked
Loading…
awarded
Loading…
awarded
1 2
3