dota吧 关注:4,645,871贴子:155,325,227

万能的dota吧啊.........对计算理论比较精通的请进.......

只看楼主收藏回复

问题1:如果P=NP,那么是否所有在P里的问题都可以互相化约?
我原本认为是可以,利用NP完全的问题的特性就可以互相化约,但是好像无法将NP完全问题转化为任意的P问题
现在更倾向于否了,但是还没找到反证,不知道有没有人能提供帮助。
问题2:已知某可计算函数f的值域有限,那么输入任何值,这个值是否在值域以内是否是可判定的?
我认为是否,但是还无法严谨的证明。
问题3:对于下面两个形式语言:
EQUAL{x,y : x,y是有效的图灵机编码,并且x,y接受的语言相等}

MIN {x :x是有效的图灵机编码,并且x的编码是最简的(相对于其他接受同样语言的图灵机而言)}
这两个语言是否能相互化约?
EQUAL < MIN很简单,但是反过来 MIN < EQUAL似乎不可能



IP属地:美国1楼2010-04-09 13:55回复
    .


    IP属地:美国2楼2010-04-09 13:57
    回复
      作为一只笨猫,我看的压力好大


      3楼2010-04-09 14:00
      回复
        .


        IP属地:美国4楼2010-04-09 14:03
        回复
          .


          IP属地:美国5楼2010-04-09 14:04
          回复
            .


            IP属地:美国7楼2010-04-09 14:08
            回复
              .


              IP属地:美国8楼2010-04-09 14:10
              回复
                .


                IP属地:美国9楼2010-04-09 14:11
                回复
                  .


                  IP属地:美国10楼2010-04-09 14:13
                  回复
                    .


                    IP属地:美国11楼2010-04-09 14:15
                    回复
                      .


                      IP属地:美国12楼2010-04-09 14:17
                      回复
                        .


                        IP属地:美国13楼2010-04-09 14:18
                        回复
                          .


                          IP属地:美国14楼2010-04-09 14:22
                          回复
                            .


                            IP属地:美国15楼2010-04-09 14:25
                            回复
                              .


                              IP属地:美国16楼2010-04-09 14:27
                              回复