Hfrhyu

Why does Kotter return in Welcome Back Kotter?

Are the number of citations and number of published articles the most important criteria for a tenure promotion?

Why Is Death Allowed In the Matrix?

Mathematical cryptic clues

Why is Minecraft giving an OpenGL error?

Languages that we cannot (dis)prove to be Context-Free

What defenses are there against being summoned by the Gate spell?

US citizen flying to France today and my passport expires in less than 2 months

Roll the carpet

Accidentally leaked the solution to an assignment, what to do now? (I'm the prof)

Hiring someone is unethical to Kantians because you're treating them as a means?

Unknown notation: What do three bars mean?

What's the output of a record cartridge playing an out-of-speed record

Fully-Firstable Anagram Sets

How to know the difference between two ciphertexts without key stream in stream ciphers

How much RAM could one put in a typical 80386 setup?

Is every diagonalizable matrix is an exponential

Smoothness of finite-dimensional functional calculus

What's the point of deactivating Num Lock on login screens?

Finding the repeating unit of polymerisation given two constituent molecules

"You are your self first supporter", a more proper way to say it

Why don't electron-positron collisions release infinite energy?

How to find program name(s) of an installed package?

What would happen to a modern skyscraper if it rains micro blackholes?

Decidable problems for which no concrete decision procedure is known

How can it be decidable whether $pi$ has some sequence of digits?Is there an algorithm that provably exists although we don't know what it is?complexity of decision problems vs computing functionsCan all decision problems reduce to undecidable?Efficiently decidable logicsWhat are some results for non-trivial lower bounds for the time complexity of decision problems?How many decidable decision problems are there?How many decision problems do exist?Are poly-reductions to PSPACE problems for following problems are known?Is there a generic procedure to produce (hard enough) decision problems?A TSP to HamCycle ReductionDecision problems involving finite automata

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

asked Apr 2 at 14:15

Jason HuJason Hu

303110

$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
  Apr 2 at 17:26
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 22:41
  

  
  
  
  

add a comment | 

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

asked Apr 2 at 14:15

Jason HuJason Hu

303110

$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
  Apr 2 at 17:26
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 22:41
  

  
  
  
  

add a comment | 

$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

asked Apr 2 at 14:15

Jason HuJason Hu

303110

$endgroup$

share|cite|improve this question

asked Apr 2 at 14:15

Jason HuJason Hu

303110

share|cite|improve this question

asked Apr 2 at 14:15

Jason HuJason Hu

303110

asked Apr 2 at 14:15

Jason HuJason Hu

303110

asked Apr 2 at 14:15

Jason HuJason Hu

303110

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 mathbbN$, 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

answered Apr 2 at 18:12

Alexey RomanovAlexey Romanov

2,2521115

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  ah I really like this sort of construction.
  $endgroup$
  – Jason Hu
  Apr 2 at 18:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 19:17
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
  $endgroup$
  – Apass.Jack
  Apr 2 at 19:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 20:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 20:39
  

  
  
  
  

 | 
show 2 more comments

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

answered Apr 2 at 14:23

Jason HuJason Hu

303110

$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
  Apr 2 at 17:13
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  In short, I am saying this answer cannot be counted as correct.
  $endgroup$
  – Apass.Jack
  Apr 2 at 17:30
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 17:34
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 17:41
  
  

  
  
  
  


• 
  
  
  

  
  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
  Apr 2 at 18:40
  

  
  
  
  

 | 
show 1 more comment

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

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

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

Name

Email

Required, but never shown

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 mathbbN$, 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

answered Apr 2 at 18:12

Alexey RomanovAlexey Romanov

2,2521115

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  ah I really like this sort of construction.
  $endgroup$
  – Jason Hu
  Apr 2 at 18:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 19:17
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
  $endgroup$
  – Apass.Jack
  Apr 2 at 19:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 20:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 20:39
  

  
  
  
  

 | 
show 2 more comments

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 mathbbN$, 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

answered Apr 2 at 18:12

Alexey RomanovAlexey Romanov

2,2521115

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  ah I really like this sort of construction.
  $endgroup$
  – Jason Hu
  Apr 2 at 18:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 19:17
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Has $P=NP$ been proved to be falsifiable in ZFC system? It looks like I am determined to confuse myself.
  $endgroup$
  – Apass.Jack
  Apr 2 at 19:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 20:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 20:39
  

  
  
  
  

 | 
show 2 more comments

$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 mathbbN$, 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

answered Apr 2 at 18:12

Alexey RomanovAlexey Romanov

2,2521115

$endgroup$

share|cite|improve this answer

answered Apr 2 at 18:12

Alexey RomanovAlexey Romanov

2,2521115

answered Apr 2 at 18:12

Alexey RomanovAlexey Romanov

2,2521115

answered Apr 2 at 18:12

Alexey RomanovAlexey Romanov

2,2521115

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

answered Apr 2 at 14:23

Jason HuJason Hu

303110

$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
  Apr 2 at 17:13
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  In short, I am saying this answer cannot be counted as correct.
  $endgroup$
  – Apass.Jack
  Apr 2 at 17:30
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 17:34
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 17:41
  
  

  
  
  
  


• 
  
  
  

  
  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
  Apr 2 at 18:40
  

  
  
  
  

 | 
show 1 more comment

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

answered Apr 2 at 14:23

Jason HuJason Hu

303110

$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
  Apr 2 at 17:13
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  In short, I am saying this answer cannot be counted as correct.
  $endgroup$
  – Apass.Jack
  Apr 2 at 17:30
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 17:34
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  Apr 2 at 17:41
  
  

  
  
  
  


• 
  
  
  

  
  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
  Apr 2 at 18:40
  

  
  
  
  

 | 
show 1 more comment

$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

answered Apr 2 at 14:23

Jason HuJason Hu

303110

$endgroup$

share|cite|improve this answer

answered Apr 2 at 14:23

Jason HuJason Hu

303110

answered Apr 2 at 14:23

Jason HuJason Hu

303110

answered Apr 2 at 14:23

Jason HuJason Hu

303110