I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$.

Since the problem will be trivial if $\beta_j > 0.5, \forall j \in J$, I can not assume that we may transform an instance to an integer one. By the way, I am looking for the computational complexity of the problem.

So my question is: How can I develop a pseudo-polynomial time algorithm for the problem (to indicate that it is at most NP-hard in the ordinary sense), although the problem is not integer-value?


Classifying algorithms as pseudo-polynomial time is not really a meaningful concept if there are no numbers (integers) in the instances. Of course, it is up to you to define what parts of the input should be considered "numbers".

Using real numbers in the inputs is a bad idea in the first place if you want to be able to analyze complexity or computability of the problem, as there is no way to encode all real numbers as finite strings from a finite alphabet.

For your problem, you may be able to turn it into an equivalent integer problem using some scaling, but it is impossible to say from the description given. Otherwise I would suggest you redefine the problem with rational parameters instead. This allows you to analyze it as a normal computational problem, and you could also meaningfully talk about pseudo-polynomial time if you, for example, consider numerators and denominators as separate integers.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the information. So you mean I should consider rational numbers for $\beta$. Then are you aware of some source that I can read to get familiar with analyzing complexity of ''normal computational problems''? $\endgroup$ – Mostafa Apr 12 '19 at 10:13
  • $\begingroup$ @Mostafa: Any textbook or introduction to computability or complexity should do. $\endgroup$ – Pontus Apr 12 '19 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.