Decidable problems for which no concrete decision procedure is known












1












$begingroup$


I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. I suppose the decidability of these problems are proved non-constructively, so that they have this kind of counter-intuitive property.



I think that in graph theory, there are a number of problems in this trait. I am wondering if you are aware of any of these.






time-complexity decision-problem







share|cite|improve this question









$endgroup$












  • $begingroup$
    I doubt there is any such kind of decidable problem, because of the definition of decidable. There are lots of decidable problems for which people do not care enough to figure out or specify a decision algorithm in its full detail. However, I would not be willing to call those situations as without known concrete decision procedure. It is more like no explicit implementation in a programming language has been done. Or is that your real intention?
    $endgroup$
    – Apass.Jack
    9 hours ago












  • $begingroup$
    Very similar questions have been considered. With a lot of confusion again! Like here: cs.stackexchange.com/questions/32325/… and here: cs.stackexchange.com/questions/367/…
    $endgroup$
    – Hendrik Jan
    4 hours ago
















1












$begingroup$


I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. I suppose the decidability of these problems are proved non-constructively, so that they have this kind of counter-intuitive property.



I think that in graph theory, there are a number of problems in this trait. I am wondering if you are aware of any of these.






time-complexity decision-problem







share|cite|improve this question









$endgroup$












  • $begingroup$
    I doubt there is any such kind of decidable problem, because of the definition of decidable. There are lots of decidable problems for which people do not care enough to figure out or specify a decision algorithm in its full detail. However, I would not be willing to call those situations as without known concrete decision procedure. It is more like no explicit implementation in a programming language has been done. Or is that your real intention?
    $endgroup$
    – Apass.Jack
    9 hours ago












  • $begingroup$
    Very similar questions have been considered. With a lot of confusion again! Like here: cs.stackexchange.com/questions/32325/… and here: cs.stackexchange.com/questions/367/…
    $endgroup$
    – Hendrik Jan
    4 hours ago














1












1








1





$begingroup$


I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. I suppose the decidability of these problems are proved non-constructively, so that they have this kind of counter-intuitive property.



I think that in graph theory, there are a number of problems in this trait. I am wondering if you are aware of any of these.






time-complexity decision-problem







share|cite|improve this question









$endgroup$




I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. I suppose the decidability of these problems are proved non-constructively, so that they have this kind of counter-intuitive property.



I think that in graph theory, there are a number of problems in this trait. I am wondering if you are aware of any of these.






time-complexity decision-problem




time-complexity decision-problem






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 13 hours ago









Jason HuJason Hu

303110




303110












  • $begingroup$
    I doubt there is any such kind of decidable problem, because of the definition of decidable. There are lots of decidable problems for which people do not care enough to figure out or specify a decision algorithm in its full detail. However, I would not be willing to call those situations as without known concrete decision procedure. It is more like no explicit implementation in a programming language has been done. Or is that your real intention?
    $endgroup$
    – Apass.Jack
    9 hours ago












  • $begingroup$
    Very similar questions have been considered. With a lot of confusion again! Like here: cs.stackexchange.com/questions/32325/… and here: cs.stackexchange.com/questions/367/…
    $endgroup$
    – Hendrik Jan
    4 hours ago


















  • $begingroup$
    I doubt there is any such kind of decidable problem, because of the definition of decidable. There are lots of decidable problems for which people do not care enough to figure out or specify a decision algorithm in its full detail. However, I would not be willing to call those situations as without known concrete decision procedure. It is more like no explicit implementation in a programming language has been done. Or is that your real intention?
    $endgroup$
    – Apass.Jack
    9 hours ago












  • $begingroup$
    Very similar questions have been considered. With a lot of confusion again! Like here: cs.stackexchange.com/questions/32325/… and here: cs.stackexchange.com/questions/367/…
    $endgroup$
    – Hendrik Jan
    4 hours ago
















$begingroup$
I doubt there is any such kind of decidable problem, because of the definition of decidable. There are lots of decidable problems for which people do not care enough to figure out or specify a decision algorithm in its full detail. However, I would not be willing to call those situations as without known concrete decision procedure. It is more like no explicit implementation in a programming language has been done. Or is that your real intention?
$endgroup$
– Apass.Jack
9 hours ago






$begingroup$
I doubt there is any such kind of decidable problem, because of the definition of decidable. There are lots of decidable problems for which people do not care enough to figure out or specify a decision algorithm in its full detail. However, I would not be willing to call those situations as without known concrete decision procedure. It is more like no explicit implementation in a programming language has been done. Or is that your real intention?
$endgroup$
– Apass.Jack
9 hours ago














$begingroup$
Very similar questions have been considered. With a lot of confusion again! Like here: cs.stackexchange.com/questions/32325/… and here: cs.stackexchange.com/questions/367/…
$endgroup$
– Hendrik Jan
4 hours ago




$begingroup$
Very similar questions have been considered. With a lot of confusion again! Like here: cs.stackexchange.com/questions/32325/… and here: cs.stackexchange.com/questions/367/…
$endgroup$
– Hendrik Jan
4 hours ago










2 Answers
2






active

oldest

votes


















2












$begingroup$

Here is a trivial example of such a problem: consider any yes-no question with an unknown answer, e.g. $P=NP$. For any $n in mathbb{N}$, let $A(n)$ be true iff $P=NP$. Then $A$ is decidable by one of two decision procedures:




  1. Always return "true".


  2. Always return "false".



But you need to solve $P=NP$ to know which one.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    ah I really like this sort of construction.
    $endgroup$
    – Jason Hu
    9 hours ago










  • $begingroup$
    In fact, some people believe $P=NP$ is undecidable. Can you prove that there is a Turing machine that will either prove or disprove $P=NP$? So the meaning of "let $A(n)$ be true iff $P=NP$" is somewhat ambiguous. What I am saying is that I would like to require that a valid or, you say, interesting example should not contain a part that is not known to be decidable from the ground, for example, ZFC system.
    $endgroup$
    – Apass.Jack
    8 hours ago












  • $begingroup$
    Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
    $endgroup$
    – Apass.Jack
    8 hours ago










  • $begingroup$
    @Apass.Jack This construction doesn't need $P=NP$ to be decidable. Taking an undecidable (in some system, e.g. in ZFC) statement would actually work a bit better: then no explicit decision procedure can ever be proven to work (in that system), as opposed to just not having one now. I am not sure exactly what you mean by "falsifiable" in the second comment.
    $endgroup$
    – Alexey Romanov
    6 hours ago










  • $begingroup$
    @Apass.Jack This might be a bit confusing because there are two different senses of "(un)decidable" involved: for logical formulas and for decision problems.
    $endgroup$
    – Alexey Romanov
    6 hours ago



















1












$begingroup$

For the record, I found the one in graph theory, which is called graph minor theorem, or Robertson–Seymour theorem.



https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem



Indeed, this theorem is proved non-constructively.






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    The truth for formidden minors is much more complicated and refined than this answer. Check is there an algorithm that finds the forbidden minors?. Note that Robertson–Seymour theorem is a theorem, not a decidable problem. It might mention a decidable problem, but it is not a decidable problem by itself. I recommend that you state the problem, the more formally the better. Explain why the problem is decidable, which might not be obvious at all and why there is no algorithm found for it, which might not be obvious at all again.
    $endgroup$
    – Apass.Jack
    10 hours ago












  • $begingroup$
    In short, I am saying this answer cannot be counted as correct.
    $endgroup$
    – Apass.Jack
    9 hours ago












  • $begingroup$
    @Apass.Jack I don't understand the theorem in its full details. I am search for an example of such kind as a concrete example, and it stops there. from wiki, it says that "As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm." I suppose it says that the poly algorithm is just unknown. what's your concern?
    $endgroup$
    – Jason Hu
    9 hours ago












  • $begingroup$
    You are talking about polynomial-time instead of decidable. These two concepts are very different. They are plenty of problems that are decidable but without polynomial-time algorithm. Did you mean to ask "decision problems that are solvable in polynomial-time for which no concrete polynomial-time algorithm is known"? That sounds like an interesting question (which might have been asked before) that makes much more sense.
    $endgroup$
    – Apass.Jack
    9 hours ago








  • 2




    $begingroup$
    @JasonHu Compare statements: 1. There's no known explicit algorithm for solving problem $X$. 2. The proof of R-S theorem doesn't provide an explicit polynomial-time algorithm for solving problem $X$. The Wikipedia only says something like 2 ("like" because as Apass.Jack says, you haven't specified the problem yet). Does this imply 1?
    $endgroup$
    – Alexey Romanov
    8 hours ago












Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106370%2fdecidable-problems-for-which-no-concrete-decision-procedure-is-known%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









2












$begingroup$

Here is a trivial example of such a problem: consider any yes-no question with an unknown answer, e.g. $P=NP$. For any $n in mathbb{N}$, let $A(n)$ be true iff $P=NP$. Then $A$ is decidable by one of two decision procedures:




  1. Always return "true".


  2. Always return "false".



But you need to solve $P=NP$ to know which one.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    ah I really like this sort of construction.
    $endgroup$
    – Jason Hu
    9 hours ago










  • $begingroup$
    In fact, some people believe $P=NP$ is undecidable. Can you prove that there is a Turing machine that will either prove or disprove $P=NP$? So the meaning of "let $A(n)$ be true iff $P=NP$" is somewhat ambiguous. What I am saying is that I would like to require that a valid or, you say, interesting example should not contain a part that is not known to be decidable from the ground, for example, ZFC system.
    $endgroup$
    – Apass.Jack
    8 hours ago












  • $begingroup$
    Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
    $endgroup$
    – Apass.Jack
    8 hours ago










  • $begingroup$
    @Apass.Jack This construction doesn't need $P=NP$ to be decidable. Taking an undecidable (in some system, e.g. in ZFC) statement would actually work a bit better: then no explicit decision procedure can ever be proven to work (in that system), as opposed to just not having one now. I am not sure exactly what you mean by "falsifiable" in the second comment.
    $endgroup$
    – Alexey Romanov
    6 hours ago










  • $begingroup$
    @Apass.Jack This might be a bit confusing because there are two different senses of "(un)decidable" involved: for logical formulas and for decision problems.
    $endgroup$
    – Alexey Romanov
    6 hours ago
















2












$begingroup$

Here is a trivial example of such a problem: consider any yes-no question with an unknown answer, e.g. $P=NP$. For any $n in mathbb{N}$, let $A(n)$ be true iff $P=NP$. Then $A$ is decidable by one of two decision procedures:




  1. Always return "true".


  2. Always return "false".



But you need to solve $P=NP$ to know which one.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    ah I really like this sort of construction.
    $endgroup$
    – Jason Hu
    9 hours ago










  • $begingroup$
    In fact, some people believe $P=NP$ is undecidable. Can you prove that there is a Turing machine that will either prove or disprove $P=NP$? So the meaning of "let $A(n)$ be true iff $P=NP$" is somewhat ambiguous. What I am saying is that I would like to require that a valid or, you say, interesting example should not contain a part that is not known to be decidable from the ground, for example, ZFC system.
    $endgroup$
    – Apass.Jack
    8 hours ago












  • $begingroup$
    Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
    $endgroup$
    – Apass.Jack
    8 hours ago










  • $begingroup$
    @Apass.Jack This construction doesn't need $P=NP$ to be decidable. Taking an undecidable (in some system, e.g. in ZFC) statement would actually work a bit better: then no explicit decision procedure can ever be proven to work (in that system), as opposed to just not having one now. I am not sure exactly what you mean by "falsifiable" in the second comment.
    $endgroup$
    – Alexey Romanov
    6 hours ago










  • $begingroup$
    @Apass.Jack This might be a bit confusing because there are two different senses of "(un)decidable" involved: for logical formulas and for decision problems.
    $endgroup$
    – Alexey Romanov
    6 hours ago














2












2








2





$begingroup$

Here is a trivial example of such a problem: consider any yes-no question with an unknown answer, e.g. $P=NP$. For any $n in mathbb{N}$, let $A(n)$ be true iff $P=NP$. Then $A$ is decidable by one of two decision procedures:




  1. Always return "true".


  2. Always return "false".



But you need to solve $P=NP$ to know which one.






share|cite|improve this answer









$endgroup$



Here is a trivial example of such a problem: consider any yes-no question with an unknown answer, e.g. $P=NP$. For any $n in mathbb{N}$, let $A(n)$ be true iff $P=NP$. Then $A$ is decidable by one of two decision procedures:




  1. Always return "true".


  2. Always return "false".



But you need to solve $P=NP$ to know which one.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 9 hours ago









Alexey RomanovAlexey Romanov

2,2521114




2,2521114












  • $begingroup$
    ah I really like this sort of construction.
    $endgroup$
    – Jason Hu
    9 hours ago










  • $begingroup$
    In fact, some people believe $P=NP$ is undecidable. Can you prove that there is a Turing machine that will either prove or disprove $P=NP$? So the meaning of "let $A(n)$ be true iff $P=NP$" is somewhat ambiguous. What I am saying is that I would like to require that a valid or, you say, interesting example should not contain a part that is not known to be decidable from the ground, for example, ZFC system.
    $endgroup$
    – Apass.Jack
    8 hours ago












  • $begingroup$
    Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
    $endgroup$
    – Apass.Jack
    8 hours ago










  • $begingroup$
    @Apass.Jack This construction doesn't need $P=NP$ to be decidable. Taking an undecidable (in some system, e.g. in ZFC) statement would actually work a bit better: then no explicit decision procedure can ever be proven to work (in that system), as opposed to just not having one now. I am not sure exactly what you mean by "falsifiable" in the second comment.
    $endgroup$
    – Alexey Romanov
    6 hours ago










  • $begingroup$
    @Apass.Jack This might be a bit confusing because there are two different senses of "(un)decidable" involved: for logical formulas and for decision problems.
    $endgroup$
    – Alexey Romanov
    6 hours ago


















  • $begingroup$
    ah I really like this sort of construction.
    $endgroup$
    – Jason Hu
    9 hours ago










  • $begingroup$
    In fact, some people believe $P=NP$ is undecidable. Can you prove that there is a Turing machine that will either prove or disprove $P=NP$? So the meaning of "let $A(n)$ be true iff $P=NP$" is somewhat ambiguous. What I am saying is that I would like to require that a valid or, you say, interesting example should not contain a part that is not known to be decidable from the ground, for example, ZFC system.
    $endgroup$
    – Apass.Jack
    8 hours ago












  • $begingroup$
    Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
    $endgroup$
    – Apass.Jack
    8 hours ago










  • $begingroup$
    @Apass.Jack This construction doesn't need $P=NP$ to be decidable. Taking an undecidable (in some system, e.g. in ZFC) statement would actually work a bit better: then no explicit decision procedure can ever be proven to work (in that system), as opposed to just not having one now. I am not sure exactly what you mean by "falsifiable" in the second comment.
    $endgroup$
    – Alexey Romanov
    6 hours ago










  • $begingroup$
    @Apass.Jack This might be a bit confusing because there are two different senses of "(un)decidable" involved: for logical formulas and for decision problems.
    $endgroup$
    – Alexey Romanov
    6 hours ago
















$begingroup$
ah I really like this sort of construction.
$endgroup$
– Jason Hu
9 hours ago




$begingroup$
ah I really like this sort of construction.
$endgroup$
– Jason Hu
9 hours ago












$begingroup$
In fact, some people believe $P=NP$ is undecidable. Can you prove that there is a Turing machine that will either prove or disprove $P=NP$? So the meaning of "let $A(n)$ be true iff $P=NP$" is somewhat ambiguous. What I am saying is that I would like to require that a valid or, you say, interesting example should not contain a part that is not known to be decidable from the ground, for example, ZFC system.
$endgroup$
– Apass.Jack
8 hours ago






$begingroup$
In fact, some people believe $P=NP$ is undecidable. Can you prove that there is a Turing machine that will either prove or disprove $P=NP$? So the meaning of "let $A(n)$ be true iff $P=NP$" is somewhat ambiguous. What I am saying is that I would like to require that a valid or, you say, interesting example should not contain a part that is not known to be decidable from the ground, for example, ZFC system.
$endgroup$
– Apass.Jack
8 hours ago














$begingroup$
Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
$endgroup$
– Apass.Jack
8 hours ago




$begingroup$
Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
$endgroup$
– Apass.Jack
8 hours ago












$begingroup$
@Apass.Jack This construction doesn't need $P=NP$ to be decidable. Taking an undecidable (in some system, e.g. in ZFC) statement would actually work a bit better: then no explicit decision procedure can ever be proven to work (in that system), as opposed to just not having one now. I am not sure exactly what you mean by "falsifiable" in the second comment.
$endgroup$
– Alexey Romanov
6 hours ago




$begingroup$
@Apass.Jack This construction doesn't need $P=NP$ to be decidable. Taking an undecidable (in some system, e.g. in ZFC) statement would actually work a bit better: then no explicit decision procedure can ever be proven to work (in that system), as opposed to just not having one now. I am not sure exactly what you mean by "falsifiable" in the second comment.
$endgroup$
– Alexey Romanov
6 hours ago












$begingroup$
@Apass.Jack This might be a bit confusing because there are two different senses of "(un)decidable" involved: for logical formulas and for decision problems.
$endgroup$
– Alexey Romanov
6 hours ago




$begingroup$
@Apass.Jack This might be a bit confusing because there are two different senses of "(un)decidable" involved: for logical formulas and for decision problems.
$endgroup$
– Alexey Romanov
6 hours ago











1












$begingroup$

For the record, I found the one in graph theory, which is called graph minor theorem, or Robertson–Seymour theorem.



https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem



Indeed, this theorem is proved non-constructively.






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    The truth for formidden minors is much more complicated and refined than this answer. Check is there an algorithm that finds the forbidden minors?. Note that Robertson–Seymour theorem is a theorem, not a decidable problem. It might mention a decidable problem, but it is not a decidable problem by itself. I recommend that you state the problem, the more formally the better. Explain why the problem is decidable, which might not be obvious at all and why there is no algorithm found for it, which might not be obvious at all again.
    $endgroup$
    – Apass.Jack
    10 hours ago












  • $begingroup$
    In short, I am saying this answer cannot be counted as correct.
    $endgroup$
    – Apass.Jack
    9 hours ago












  • $begingroup$
    @Apass.Jack I don't understand the theorem in its full details. I am search for an example of such kind as a concrete example, and it stops there. from wiki, it says that "As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm." I suppose it says that the poly algorithm is just unknown. what's your concern?
    $endgroup$
    – Jason Hu
    9 hours ago












  • $begingroup$
    You are talking about polynomial-time instead of decidable. These two concepts are very different. They are plenty of problems that are decidable but without polynomial-time algorithm. Did you mean to ask "decision problems that are solvable in polynomial-time for which no concrete polynomial-time algorithm is known"? That sounds like an interesting question (which might have been asked before) that makes much more sense.
    $endgroup$
    – Apass.Jack
    9 hours ago








  • 2




    $begingroup$
    @JasonHu Compare statements: 1. There's no known explicit algorithm for solving problem $X$. 2. The proof of R-S theorem doesn't provide an explicit polynomial-time algorithm for solving problem $X$. The Wikipedia only says something like 2 ("like" because as Apass.Jack says, you haven't specified the problem yet). Does this imply 1?
    $endgroup$
    – Alexey Romanov
    8 hours ago
















1












$begingroup$

For the record, I found the one in graph theory, which is called graph minor theorem, or Robertson–Seymour theorem.



https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem



Indeed, this theorem is proved non-constructively.






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    The truth for formidden minors is much more complicated and refined than this answer. Check is there an algorithm that finds the forbidden minors?. Note that Robertson–Seymour theorem is a theorem, not a decidable problem. It might mention a decidable problem, but it is not a decidable problem by itself. I recommend that you state the problem, the more formally the better. Explain why the problem is decidable, which might not be obvious at all and why there is no algorithm found for it, which might not be obvious at all again.
    $endgroup$
    – Apass.Jack
    10 hours ago












  • $begingroup$
    In short, I am saying this answer cannot be counted as correct.
    $endgroup$
    – Apass.Jack
    9 hours ago












  • $begingroup$
    @Apass.Jack I don't understand the theorem in its full details. I am search for an example of such kind as a concrete example, and it stops there. from wiki, it says that "As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm." I suppose it says that the poly algorithm is just unknown. what's your concern?
    $endgroup$
    – Jason Hu
    9 hours ago












  • $begingroup$
    You are talking about polynomial-time instead of decidable. These two concepts are very different. They are plenty of problems that are decidable but without polynomial-time algorithm. Did you mean to ask "decision problems that are solvable in polynomial-time for which no concrete polynomial-time algorithm is known"? That sounds like an interesting question (which might have been asked before) that makes much more sense.
    $endgroup$
    – Apass.Jack
    9 hours ago








  • 2




    $begingroup$
    @JasonHu Compare statements: 1. There's no known explicit algorithm for solving problem $X$. 2. The proof of R-S theorem doesn't provide an explicit polynomial-time algorithm for solving problem $X$. The Wikipedia only says something like 2 ("like" because as Apass.Jack says, you haven't specified the problem yet). Does this imply 1?
    $endgroup$
    – Alexey Romanov
    8 hours ago














1












1








1





$begingroup$

For the record, I found the one in graph theory, which is called graph minor theorem, or Robertson–Seymour theorem.



https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem



Indeed, this theorem is proved non-constructively.






share|cite|improve this answer









$endgroup$



For the record, I found the one in graph theory, which is called graph minor theorem, or Robertson–Seymour theorem.



https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem



Indeed, this theorem is proved non-constructively.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 13 hours ago









Jason HuJason Hu

303110




303110








  • 2




    $begingroup$
    The truth for formidden minors is much more complicated and refined than this answer. Check is there an algorithm that finds the forbidden minors?. Note that Robertson–Seymour theorem is a theorem, not a decidable problem. It might mention a decidable problem, but it is not a decidable problem by itself. I recommend that you state the problem, the more formally the better. Explain why the problem is decidable, which might not be obvious at all and why there is no algorithm found for it, which might not be obvious at all again.
    $endgroup$
    – Apass.Jack
    10 hours ago












  • $begingroup$
    In short, I am saying this answer cannot be counted as correct.
    $endgroup$
    – Apass.Jack
    9 hours ago












  • $begingroup$
    @Apass.Jack I don't understand the theorem in its full details. I am search for an example of such kind as a concrete example, and it stops there. from wiki, it says that "As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm." I suppose it says that the poly algorithm is just unknown. what's your concern?
    $endgroup$
    – Jason Hu
    9 hours ago












  • $begingroup$
    You are talking about polynomial-time instead of decidable. These two concepts are very different. They are plenty of problems that are decidable but without polynomial-time algorithm. Did you mean to ask "decision problems that are solvable in polynomial-time for which no concrete polynomial-time algorithm is known"? That sounds like an interesting question (which might have been asked before) that makes much more sense.
    $endgroup$
    – Apass.Jack
    9 hours ago








  • 2




    $begingroup$
    @JasonHu Compare statements: 1. There's no known explicit algorithm for solving problem $X$. 2. The proof of R-S theorem doesn't provide an explicit polynomial-time algorithm for solving problem $X$. The Wikipedia only says something like 2 ("like" because as Apass.Jack says, you haven't specified the problem yet). Does this imply 1?
    $endgroup$
    – Alexey Romanov
    8 hours ago














  • 2




    $begingroup$
    The truth for formidden minors is much more complicated and refined than this answer. Check is there an algorithm that finds the forbidden minors?. Note that Robertson–Seymour theorem is a theorem, not a decidable problem. It might mention a decidable problem, but it is not a decidable problem by itself. I recommend that you state the problem, the more formally the better. Explain why the problem is decidable, which might not be obvious at all and why there is no algorithm found for it, which might not be obvious at all again.
    $endgroup$
    – Apass.Jack
    10 hours ago












  • $begingroup$
    In short, I am saying this answer cannot be counted as correct.
    $endgroup$
    – Apass.Jack
    9 hours ago












  • $begingroup$
    @Apass.Jack I don't understand the theorem in its full details. I am search for an example of such kind as a concrete example, and it stops there. from wiki, it says that "As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm." I suppose it says that the poly algorithm is just unknown. what's your concern?
    $endgroup$
    – Jason Hu
    9 hours ago












  • $begingroup$
    You are talking about polynomial-time instead of decidable. These two concepts are very different. They are plenty of problems that are decidable but without polynomial-time algorithm. Did you mean to ask "decision problems that are solvable in polynomial-time for which no concrete polynomial-time algorithm is known"? That sounds like an interesting question (which might have been asked before) that makes much more sense.
    $endgroup$
    – Apass.Jack
    9 hours ago








  • 2




    $begingroup$
    @JasonHu Compare statements: 1. There's no known explicit algorithm for solving problem $X$. 2. The proof of R-S theorem doesn't provide an explicit polynomial-time algorithm for solving problem $X$. The Wikipedia only says something like 2 ("like" because as Apass.Jack says, you haven't specified the problem yet). Does this imply 1?
    $endgroup$
    – Alexey Romanov
    8 hours ago








2




2




$begingroup$
The truth for formidden minors is much more complicated and refined than this answer. Check is there an algorithm that finds the forbidden minors?. Note that Robertson–Seymour theorem is a theorem, not a decidable problem. It might mention a decidable problem, but it is not a decidable problem by itself. I recommend that you state the problem, the more formally the better. Explain why the problem is decidable, which might not be obvious at all and why there is no algorithm found for it, which might not be obvious at all again.
$endgroup$
– Apass.Jack
10 hours ago






$begingroup$
The truth for formidden minors is much more complicated and refined than this answer. Check is there an algorithm that finds the forbidden minors?. Note that Robertson–Seymour theorem is a theorem, not a decidable problem. It might mention a decidable problem, but it is not a decidable problem by itself. I recommend that you state the problem, the more formally the better. Explain why the problem is decidable, which might not be obvious at all and why there is no algorithm found for it, which might not be obvious at all again.
$endgroup$
– Apass.Jack
10 hours ago














$begingroup$
In short, I am saying this answer cannot be counted as correct.
$endgroup$
– Apass.Jack
9 hours ago






$begingroup$
In short, I am saying this answer cannot be counted as correct.
$endgroup$
– Apass.Jack
9 hours ago














$begingroup$
@Apass.Jack I don't understand the theorem in its full details. I am search for an example of such kind as a concrete example, and it stops there. from wiki, it says that "As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm." I suppose it says that the poly algorithm is just unknown. what's your concern?
$endgroup$
– Jason Hu
9 hours ago






$begingroup$
@Apass.Jack I don't understand the theorem in its full details. I am search for an example of such kind as a concrete example, and it stops there. from wiki, it says that "As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm." I suppose it says that the poly algorithm is just unknown. what's your concern?
$endgroup$
– Jason Hu
9 hours ago














$begingroup$
You are talking about polynomial-time instead of decidable. These two concepts are very different. They are plenty of problems that are decidable but without polynomial-time algorithm. Did you mean to ask "decision problems that are solvable in polynomial-time for which no concrete polynomial-time algorithm is known"? That sounds like an interesting question (which might have been asked before) that makes much more sense.
$endgroup$
– Apass.Jack
9 hours ago






$begingroup$
You are talking about polynomial-time instead of decidable. These two concepts are very different. They are plenty of problems that are decidable but without polynomial-time algorithm. Did you mean to ask "decision problems that are solvable in polynomial-time for which no concrete polynomial-time algorithm is known"? That sounds like an interesting question (which might have been asked before) that makes much more sense.
$endgroup$
– Apass.Jack
9 hours ago






2




2




$begingroup$
@JasonHu Compare statements: 1. There's no known explicit algorithm for solving problem $X$. 2. The proof of R-S theorem doesn't provide an explicit polynomial-time algorithm for solving problem $X$. The Wikipedia only says something like 2 ("like" because as Apass.Jack says, you haven't specified the problem yet). Does this imply 1?
$endgroup$
– Alexey Romanov
8 hours ago




$begingroup$
@JasonHu Compare statements: 1. There's no known explicit algorithm for solving problem $X$. 2. The proof of R-S theorem doesn't provide an explicit polynomial-time algorithm for solving problem $X$. The Wikipedia only says something like 2 ("like" because as Apass.Jack says, you haven't specified the problem yet). Does this imply 1?
$endgroup$
– Alexey Romanov
8 hours ago


















draft saved

draft discarded




















































Thanks for contributing an answer to Computer Science Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106370%2fdecidable-problems-for-which-no-concrete-decision-procedure-is-known%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

Image
0 I found a lot of questions abount appendices and ToC. Many users want appendices to be grouped in an Appendix part, however some problems arise with ToC, hyperref, PDF viewer bookmarks, and so on. There are different solutions which require extra packages, command patching and other extra code, however none of them satisfies me. I almost found an easy way to accomplish a good result, where appendices are added to bookmarks in the right way and hyperref links point to the right page. However, the number of the "Appendix" part page is wrong (it's the number of appendix A). Is there any EASY way to fix that? This is a MWE: documentclass{book} usepackage[nottoc,notlot,notlof]{tocbibind} usepackage{hyperref} begin{document} frontmatter tableofcontents mainmatter part{First} chapter{...
Read more

Calculate evaluation metrics using cross_val_predict sklearn

Image
1 In the sklearn.model_selection.cross_val_predict page it is stated: Generate cross-validated estimates for each input data point. It is not appropriate to pass these predictions into an evaluation metric. Can someone explain what does it mean? If this gives estimate of Y (y prediction) for every Y (true Y), why can't I calculate metrics such as RMSE or coefficient of determination using these results? python scikit-learn cross-validation share | improve this question edited Nov 28 '18 at 17:52 desertnaut 20.3k 7 43 79 ...
Read more

Insert data from modal to MySQL (multiple modal on website)

Image
0 I have problem with inserting data to MySQL from modal. My modal: <a href="#" class="badge badge-pill badge-success">6 komentarzy</a> <a href="#" class="badge badge-pill badge-danger">brak komentarzy</a> <a data-toggle="modal" href="#add_desk_comm_{$desk_['desk_id']}" data-target="#add_desk_comm_{$desk_['desk_id']}" class="ediiit">(dodaj)</a> <div class="modal fade" id="add_desk_comm_{$desk_['desk_id']}" tabindex="-1" role="dialog" aria-labelledby="edit_printer" aria-hidden="true"> <div class="modal-dialog" role="document"> ...
Read more