How are problems classified in Complexity Theory? The Next CEO of Stack OverflowWhy are decision problems commonly used in complexity theory?Negligible Function in CryptographyComputational complexity theory booksHow does “language” relate to “problem” in complexity theory?Open problems in complexity theoryProblem in Papadimitriou's “Computational Complexity” seems oddProblems in Complexity TheoryVerifier - Complexity TheoryProblems that feel exponential but are PMany-One Reducibility of decision problems for complexity theory?

How to count occurrences of text in a file?

Example of a Mathematician/Physicist whose Other Publications during their PhD eclipsed their PhD Thesis

Find non-case sensitive string in a mixed list of elements?

How to check if all elements of 1 list are in the *same quantity* and in any order, in the list2?

Poetry, calligrams and TikZ/PStricks challenge

Why isn't the Mueller report being released completely and unredacted?

Bartok - Syncopation (1): Meaning of notes in between Grand Staff

How to avoid supervisors with prejudiced views?

If Nick Fury and Coulson already knew about aliens (Kree and Skrull) why did they wait until Thor's appearance to start making weapons?

Can we say or write : "No, it'sn't"?

How to delete every two lines after 3rd lines in a file contains very large number of lines?

How to edit “Name” property in GCI output?

Can MTA send mail via a relay without being told so?

How to get from Geneva Airport to Metabief, Doubs, France by public transport?

TikZ: How to reverse arrow direction without switching start/end point?

When you upcast Blindness/Deafness, do all targets suffer the same effect?

How do I align (1) and (2)?

Does soap repel water?

How I can get glyphs from a fraktur font and use them as identifiers?

The exact meaning of 'Mom made me a sandwich'

Are police here, aren't itthey?

A small doubt about the dominated convergence theorem

Won the lottery - how do I keep the money?

Why do remote US companies require working in the US?



How are problems classified in Complexity Theory?



The Next CEO of Stack OverflowWhy are decision problems commonly used in complexity theory?Negligible Function in CryptographyComputational complexity theory booksHow does “language” relate to “problem” in complexity theory?Open problems in complexity theoryProblem in Papadimitriou's “Computational Complexity” seems oddProblems in Complexity TheoryVerifier - Complexity TheoryProblems that feel exponential but are PMany-One Reducibility of decision problems for complexity theory?










1












$begingroup$


I'm reading Sipser's Introduction to the Theory of Computation (3rd edition). In chapter 0 (pg. 2), he says we don't know the answer to "what makes some problems computationally hard and others easy," however, he then states that "researchers have
discovered an elegant scheme for classifying problems according to their computational difficulty. Using this scheme, we can demonstrate
a method for giving evidence that certain problems are computationally hard,
even if we are unable to prove that they are.
"



So my question is: HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?



Also, what/where is this "scheme" that does this classifying. (I did some googling and couldn't find anything)










share|cite|improve this question







New contributor




Johan von Adden is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$
















    1












    $begingroup$


    I'm reading Sipser's Introduction to the Theory of Computation (3rd edition). In chapter 0 (pg. 2), he says we don't know the answer to "what makes some problems computationally hard and others easy," however, he then states that "researchers have
    discovered an elegant scheme for classifying problems according to their computational difficulty. Using this scheme, we can demonstrate
    a method for giving evidence that certain problems are computationally hard,
    even if we are unable to prove that they are.
    "



    So my question is: HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?



    Also, what/where is this "scheme" that does this classifying. (I did some googling and couldn't find anything)










    share|cite|improve this question







    New contributor




    Johan von Adden is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$














      1












      1








      1





      $begingroup$


      I'm reading Sipser's Introduction to the Theory of Computation (3rd edition). In chapter 0 (pg. 2), he says we don't know the answer to "what makes some problems computationally hard and others easy," however, he then states that "researchers have
      discovered an elegant scheme for classifying problems according to their computational difficulty. Using this scheme, we can demonstrate
      a method for giving evidence that certain problems are computationally hard,
      even if we are unable to prove that they are.
      "



      So my question is: HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?



      Also, what/where is this "scheme" that does this classifying. (I did some googling and couldn't find anything)










      share|cite|improve this question







      New contributor




      Johan von Adden is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      I'm reading Sipser's Introduction to the Theory of Computation (3rd edition). In chapter 0 (pg. 2), he says we don't know the answer to "what makes some problems computationally hard and others easy," however, he then states that "researchers have
      discovered an elegant scheme for classifying problems according to their computational difficulty. Using this scheme, we can demonstrate
      a method for giving evidence that certain problems are computationally hard,
      even if we are unable to prove that they are.
      "



      So my question is: HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?



      Also, what/where is this "scheme" that does this classifying. (I did some googling and couldn't find anything)







      complexity-theory






      share|cite|improve this question







      New contributor




      Johan von Adden is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|cite|improve this question







      New contributor




      Johan von Adden is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|cite|improve this question




      share|cite|improve this question






      New contributor




      Johan von Adden is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked yesterday









      Johan von AddenJohan von Adden

      82




      82




      New contributor




      Johan von Adden is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Johan von Adden is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Johan von Adden is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.




















          3 Answers
          3






          active

          oldest

          votes


















          9












          $begingroup$

          That's what you get when you distill a whole bunch of theory to a wider audience.



          In his book, Sipser addresses a general audience at the undergraduate level, possibly with no notion of computability theory; hence, he can only hint at concepts which are to be given a more formal treatment later on in the book. The part you cite is from chapter 0 (i.e., not really a chapter), whereas the material for complexity theory only appears at the end (i.e., part three). This is why the passage is so fuzzy. Most likely it is intended only as motivation and to give a broad overview for the topics to be covered in the book.



          The "scheme" Sipser is talking about are reductions. If we know a problem $A$ is reducible to a problem $B$, then we know $B$ is at least as hard as $A$. (Incidentally, this is also why it is common practice to denote reductions with a "$le$" sign.) This gives us a way of ordering problems according to their difficulty, at least for those having reductions we are aware of. As Sipser states, though, by using only reductions "we are unable to prove" whether the problems are really hard or not; reductions only give us relative, not absolute notions of hardness. This is why separation results are still rare in modern complexity theory: We have a bunch of reduction (e.g., NP-completeness) results, but only a handful of separation results (e.g., the time and space hierarchy theorems).






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            I appreciate the thorough answer. Vincenzo (one of the commentors) mentioned that Sipser discusses this in Ch 5 & 7, which I'll hopefully get to eventually!
            $endgroup$
            – Johan von Adden
            yesterday


















          2












          $begingroup$


          HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?




          I think the point that the piece is trying to make is that we know how to determine whether individual problems are easy or hard, even though we don't have an over-arching theory of why the hard ones are hard and the easy ones are easy. Just like you can classify people according to their weight, even though you don't know why they have the weight they do.



          I should emphasise that in most cases, "hard" means "seem to be hard". You've probably heard of NP-complete problems. We don't know for certain that these problems have no efficient algorithm (by the standard definition of "efficient") but nobody has been able find an efficient algorithm for any of them in nearly 50 years of trying, and finding an efficient algorithm for just one of them would give efficient algorithms for all of them.




          Also, what/where is this "scheme"




          Complexity classes, the relationships between them, and the concept of reductions for transforming one problem into another.






          share|cite|improve this answer











          $endgroup$




















            1












            $begingroup$

            The "scheme" is based on the ideas of reductions among problems and completeness of problems, which are described in Chapters 5 and 7 of Sipser's book.






            share|cite|improve this answer









            $endgroup$













              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
              );



              );






              Johan von Adden is a new contributor. Be nice, and check out our Code of Conduct.









              draft saved

              draft discarded


















              StackExchange.ready(
              function ()
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106207%2fhow-are-problems-classified-in-complexity-theory%23new-answer', 'question_page');

              );

              Post as a guest















              Required, but never shown

























              3 Answers
              3






              active

              oldest

              votes








              3 Answers
              3






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              9












              $begingroup$

              That's what you get when you distill a whole bunch of theory to a wider audience.



              In his book, Sipser addresses a general audience at the undergraduate level, possibly with no notion of computability theory; hence, he can only hint at concepts which are to be given a more formal treatment later on in the book. The part you cite is from chapter 0 (i.e., not really a chapter), whereas the material for complexity theory only appears at the end (i.e., part three). This is why the passage is so fuzzy. Most likely it is intended only as motivation and to give a broad overview for the topics to be covered in the book.



              The "scheme" Sipser is talking about are reductions. If we know a problem $A$ is reducible to a problem $B$, then we know $B$ is at least as hard as $A$. (Incidentally, this is also why it is common practice to denote reductions with a "$le$" sign.) This gives us a way of ordering problems according to their difficulty, at least for those having reductions we are aware of. As Sipser states, though, by using only reductions "we are unable to prove" whether the problems are really hard or not; reductions only give us relative, not absolute notions of hardness. This is why separation results are still rare in modern complexity theory: We have a bunch of reduction (e.g., NP-completeness) results, but only a handful of separation results (e.g., the time and space hierarchy theorems).






              share|cite|improve this answer











              $endgroup$












              • $begingroup$
                I appreciate the thorough answer. Vincenzo (one of the commentors) mentioned that Sipser discusses this in Ch 5 & 7, which I'll hopefully get to eventually!
                $endgroup$
                – Johan von Adden
                yesterday















              9












              $begingroup$

              That's what you get when you distill a whole bunch of theory to a wider audience.



              In his book, Sipser addresses a general audience at the undergraduate level, possibly with no notion of computability theory; hence, he can only hint at concepts which are to be given a more formal treatment later on in the book. The part you cite is from chapter 0 (i.e., not really a chapter), whereas the material for complexity theory only appears at the end (i.e., part three). This is why the passage is so fuzzy. Most likely it is intended only as motivation and to give a broad overview for the topics to be covered in the book.



              The "scheme" Sipser is talking about are reductions. If we know a problem $A$ is reducible to a problem $B$, then we know $B$ is at least as hard as $A$. (Incidentally, this is also why it is common practice to denote reductions with a "$le$" sign.) This gives us a way of ordering problems according to their difficulty, at least for those having reductions we are aware of. As Sipser states, though, by using only reductions "we are unable to prove" whether the problems are really hard or not; reductions only give us relative, not absolute notions of hardness. This is why separation results are still rare in modern complexity theory: We have a bunch of reduction (e.g., NP-completeness) results, but only a handful of separation results (e.g., the time and space hierarchy theorems).






              share|cite|improve this answer











              $endgroup$












              • $begingroup$
                I appreciate the thorough answer. Vincenzo (one of the commentors) mentioned that Sipser discusses this in Ch 5 & 7, which I'll hopefully get to eventually!
                $endgroup$
                – Johan von Adden
                yesterday













              9












              9








              9





              $begingroup$

              That's what you get when you distill a whole bunch of theory to a wider audience.



              In his book, Sipser addresses a general audience at the undergraduate level, possibly with no notion of computability theory; hence, he can only hint at concepts which are to be given a more formal treatment later on in the book. The part you cite is from chapter 0 (i.e., not really a chapter), whereas the material for complexity theory only appears at the end (i.e., part three). This is why the passage is so fuzzy. Most likely it is intended only as motivation and to give a broad overview for the topics to be covered in the book.



              The "scheme" Sipser is talking about are reductions. If we know a problem $A$ is reducible to a problem $B$, then we know $B$ is at least as hard as $A$. (Incidentally, this is also why it is common practice to denote reductions with a "$le$" sign.) This gives us a way of ordering problems according to their difficulty, at least for those having reductions we are aware of. As Sipser states, though, by using only reductions "we are unable to prove" whether the problems are really hard or not; reductions only give us relative, not absolute notions of hardness. This is why separation results are still rare in modern complexity theory: We have a bunch of reduction (e.g., NP-completeness) results, but only a handful of separation results (e.g., the time and space hierarchy theorems).






              share|cite|improve this answer











              $endgroup$



              That's what you get when you distill a whole bunch of theory to a wider audience.



              In his book, Sipser addresses a general audience at the undergraduate level, possibly with no notion of computability theory; hence, he can only hint at concepts which are to be given a more formal treatment later on in the book. The part you cite is from chapter 0 (i.e., not really a chapter), whereas the material for complexity theory only appears at the end (i.e., part three). This is why the passage is so fuzzy. Most likely it is intended only as motivation and to give a broad overview for the topics to be covered in the book.



              The "scheme" Sipser is talking about are reductions. If we know a problem $A$ is reducible to a problem $B$, then we know $B$ is at least as hard as $A$. (Incidentally, this is also why it is common practice to denote reductions with a "$le$" sign.) This gives us a way of ordering problems according to their difficulty, at least for those having reductions we are aware of. As Sipser states, though, by using only reductions "we are unable to prove" whether the problems are really hard or not; reductions only give us relative, not absolute notions of hardness. This is why separation results are still rare in modern complexity theory: We have a bunch of reduction (e.g., NP-completeness) results, but only a handful of separation results (e.g., the time and space hierarchy theorems).







              share|cite|improve this answer














              share|cite|improve this answer



              share|cite|improve this answer








              edited yesterday

























              answered yesterday









              dkaeaedkaeae

              2,2071922




              2,2071922











              • $begingroup$
                I appreciate the thorough answer. Vincenzo (one of the commentors) mentioned that Sipser discusses this in Ch 5 & 7, which I'll hopefully get to eventually!
                $endgroup$
                – Johan von Adden
                yesterday
















              • $begingroup$
                I appreciate the thorough answer. Vincenzo (one of the commentors) mentioned that Sipser discusses this in Ch 5 & 7, which I'll hopefully get to eventually!
                $endgroup$
                – Johan von Adden
                yesterday















              $begingroup$
              I appreciate the thorough answer. Vincenzo (one of the commentors) mentioned that Sipser discusses this in Ch 5 & 7, which I'll hopefully get to eventually!
              $endgroup$
              – Johan von Adden
              yesterday




              $begingroup$
              I appreciate the thorough answer. Vincenzo (one of the commentors) mentioned that Sipser discusses this in Ch 5 & 7, which I'll hopefully get to eventually!
              $endgroup$
              – Johan von Adden
              yesterday











              2












              $begingroup$


              HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?




              I think the point that the piece is trying to make is that we know how to determine whether individual problems are easy or hard, even though we don't have an over-arching theory of why the hard ones are hard and the easy ones are easy. Just like you can classify people according to their weight, even though you don't know why they have the weight they do.



              I should emphasise that in most cases, "hard" means "seem to be hard". You've probably heard of NP-complete problems. We don't know for certain that these problems have no efficient algorithm (by the standard definition of "efficient") but nobody has been able find an efficient algorithm for any of them in nearly 50 years of trying, and finding an efficient algorithm for just one of them would give efficient algorithms for all of them.




              Also, what/where is this "scheme"




              Complexity classes, the relationships between them, and the concept of reductions for transforming one problem into another.






              share|cite|improve this answer











              $endgroup$

















                2












                $begingroup$


                HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?




                I think the point that the piece is trying to make is that we know how to determine whether individual problems are easy or hard, even though we don't have an over-arching theory of why the hard ones are hard and the easy ones are easy. Just like you can classify people according to their weight, even though you don't know why they have the weight they do.



                I should emphasise that in most cases, "hard" means "seem to be hard". You've probably heard of NP-complete problems. We don't know for certain that these problems have no efficient algorithm (by the standard definition of "efficient") but nobody has been able find an efficient algorithm for any of them in nearly 50 years of trying, and finding an efficient algorithm for just one of them would give efficient algorithms for all of them.




                Also, what/where is this "scheme"




                Complexity classes, the relationships between them, and the concept of reductions for transforming one problem into another.






                share|cite|improve this answer











                $endgroup$















                  2












                  2








                  2





                  $begingroup$


                  HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?




                  I think the point that the piece is trying to make is that we know how to determine whether individual problems are easy or hard, even though we don't have an over-arching theory of why the hard ones are hard and the easy ones are easy. Just like you can classify people according to their weight, even though you don't know why they have the weight they do.



                  I should emphasise that in most cases, "hard" means "seem to be hard". You've probably heard of NP-complete problems. We don't know for certain that these problems have no efficient algorithm (by the standard definition of "efficient") but nobody has been able find an efficient algorithm for any of them in nearly 50 years of trying, and finding an efficient algorithm for just one of them would give efficient algorithms for all of them.




                  Also, what/where is this "scheme"




                  Complexity classes, the relationships between them, and the concept of reductions for transforming one problem into another.






                  share|cite|improve this answer











                  $endgroup$




                  HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?




                  I think the point that the piece is trying to make is that we know how to determine whether individual problems are easy or hard, even though we don't have an over-arching theory of why the hard ones are hard and the easy ones are easy. Just like you can classify people according to their weight, even though you don't know why they have the weight they do.



                  I should emphasise that in most cases, "hard" means "seem to be hard". You've probably heard of NP-complete problems. We don't know for certain that these problems have no efficient algorithm (by the standard definition of "efficient") but nobody has been able find an efficient algorithm for any of them in nearly 50 years of trying, and finding an efficient algorithm for just one of them would give efficient algorithms for all of them.




                  Also, what/where is this "scheme"




                  Complexity classes, the relationships between them, and the concept of reductions for transforming one problem into another.







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited yesterday

























                  answered yesterday









                  David RicherbyDavid Richerby

                  69.3k15106195




                  69.3k15106195





















                      1












                      $begingroup$

                      The "scheme" is based on the ideas of reductions among problems and completeness of problems, which are described in Chapters 5 and 7 of Sipser's book.






                      share|cite|improve this answer









                      $endgroup$

















                        1












                        $begingroup$

                        The "scheme" is based on the ideas of reductions among problems and completeness of problems, which are described in Chapters 5 and 7 of Sipser's book.






                        share|cite|improve this answer









                        $endgroup$















                          1












                          1








                          1





                          $begingroup$

                          The "scheme" is based on the ideas of reductions among problems and completeness of problems, which are described in Chapters 5 and 7 of Sipser's book.






                          share|cite|improve this answer









                          $endgroup$



                          The "scheme" is based on the ideas of reductions among problems and completeness of problems, which are described in Chapters 5 and 7 of Sipser's book.







                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered yesterday









                          VincenzoVincenzo

                          2,0651614




                          2,0651614




















                              Johan von Adden is a new contributor. Be nice, and check out our Code of Conduct.









                              draft saved

                              draft discarded


















                              Johan von Adden is a new contributor. Be nice, and check out our Code of Conduct.












                              Johan von Adden is a new contributor. Be nice, and check out our Code of Conduct.











                              Johan von Adden is a new contributor. Be nice, and check out our Code of Conduct.














                              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%2f106207%2fhow-are-problems-classified-in-complexity-theory%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

                              Wikipedia:Vital articles Мазмуну Biography - Өмүр баян Philosophy and psychology - Философия жана психология Religion - Дин Social sciences - Коомдук илимдер Language and literature - Тил жана адабият Science - Илим Technology - Технология Arts and recreation - Искусство жана эс алуу History and geography - Тарых жана география Навигация менюсу

                              Bruxelas-Capital Índice Historia | Composición | Situación lingüística | Clima | Cidades irmandadas | Notas | Véxase tamén | Menú de navegacióneO uso das linguas en Bruxelas e a situación do neerlandés"Rexión de Bruxelas Capital"o orixinalSitio da rexiónPáxina de Bruselas no sitio da Oficina de Promoción Turística de Valonia e BruxelasMapa Interactivo da Rexión de Bruxelas-CapitaleeWorldCat332144929079854441105155190212ID28008674080552-90000 0001 0666 3698n94104302ID540940339365017018237

                              What should I write in an apology letter, since I have decided not to join a company after accepting an offer letterShould I keep looking after accepting a job offer?What should I do when I've been verbally told I would get an offer letter, but still haven't gotten one after 4 weeks?Do I accept an offer from a company that I am not likely to join?New job hasn't confirmed starting date and I want to give current employer as much notice as possibleHow should I address my manager in my resignation letter?HR delayed background verification, now jobless as resignedNo email communication after accepting a formal written offer. How should I phrase the call?What should I do if after receiving a verbal offer letter I am informed that my written job offer is put on hold due to some internal issues?Should I inform the current employer that I am about to resign within 1-2 weeks since I have signed the offer letter and waiting for visa?What company will do, if I send their offer letter to another company