Member Avatar for Saiiiira

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.

  • 2 Contributors
  • 2 Replies
  • 133 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Saiiiira

Recommended Answers

All 2 Replies

Member Avatar for Rashakil Fol

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

Edited by Rashakil Fol because: n/a
Member Avatar for Saiiiira

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

Be a part of the DaniWeb community

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