Hi.
If I define Poly-time functions, the functions that are computable by a turing machine in maximum polynomial(n) time, which n is size of input. Is the class of these functions recursively enumerable?

I think that this Poly-time is the famous P-class in complexity,but as I searched I didn't find anything discussing wether this class is RE....My question comes from here:I read that the class of recursive functions is not RE,so I thought that maybe it's subclasses would be,the most natural subclass that came to my mind was this Poly-time functions class...

Thanks very much.

Recommended Answers

I doubt it, but I don't have a convincing proof on hand.

Jump to Post

All 2 Replies

I doubt it, but I don't have a convincing proof on hand.

Thank you very much:)
Yes it is!solved!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.19 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.