Post Closed as "not a real question" by Kaveh, Pål GD, frafl, Yuval Filmus, Ran G. occurred Apr 20 '13 at 20:27 5 Modification to the question by arithmetic edit approved Apr 16 '13 at 15:12 arithmetic 522 bronze badges There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class? For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity? By converting into elementary recursive form, I mean: Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form. By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else". Modification to the question: Let us say that for all decision problems we consider, there exist function problems that have same time complexity as their decision problem counterparts. For example, for 3-SAT problem with some input $$x$$, one satisfying assignment to the variables is treated as output. The reason why some people think this question is not valuable may be because for all decision problems, output is always either zero or one. So let us consider the function version of decision problems (that keeps time complexity). There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class? For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity? By converting into elementary recursive form, I mean: Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form. By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else". There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class? For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity? By converting into elementary recursive form, I mean: Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form. By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else". Modification to the question: Let us say that for all decision problems we consider, there exist function problems that have same time complexity as their decision problem counterparts. For example, for 3-SAT problem with some input $$x$$, one satisfying assignment to the variables is treated as output. The reason why some people think this question is not valuable may be because for all decision problems, output is always either zero or one. So let us consider the function version of decision problems (that keeps time complexity). 4 Editing as another account. edited Apr 16 '13 at 9:20 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class? For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity? I lost my account, so I have to write as another account. By converting into elementary recursive form, I mean: Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form. By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else". There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class? For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity? I lost my account, so I have to write as another account. By converting into elementary recursive form, I mean: Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form. By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else". There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class? For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity? By converting into elementary recursive form, I mean: Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form. By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else". 3 Editing as another account. edit approved Apr 16 '13 at 9:20 arithmetic 522 bronze badges There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class? For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity? I lost my account, so I have to write as another account. By converting into elementary recursive form, I mean: Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form. By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else". There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class? For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity? There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class? For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity? I lost my account, so I have to write as another account. By converting into elementary recursive form, I mean: Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form. By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else". 2 language and title edited Apr 14 '13 at 11:26 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges Tweeted twitter.com/#!/StackCompSci/status/323343846442426368 occurred Apr 14 '13 at 7:55 1 asked Apr 14 '13 at 6:57 arithmetic 711 bronze badge