VS_VF

Prévia do material em texto

(V) Dizemos que um problema Π pertence à classe NP dos problemas de decisão se tivermos alg. não-deterministico polinomial para Π.
(V) Um problema pertence a classe P dos problemas de decisão se existir alg. Que resolve em tempo polinomial.
(V) Um problema Π1 é redutível a um problema Π2, se para qualquer instância de Π1, uma instância de Π2 poderá ser construída em tempo polinomial tal que resolvendo Π2 resolve-se implicitamente Π1.
(V) A redutibilidade de Π1 e Π2 implica que Π1 pode ser considerado caso particular de Π2.
(V) Se Π1 α Π2 e Π2 α Π1, dizemos que os problemas são equivalentes.
(V) A redutibilidade é uma relação transitiva, assim se Π1 α Π2 e Π2 α Π3 então Π1 α Π3.
(V) Um problema de decisão é NP-Árduo se Π’ é redutível a Π qualquer que seja Π’ pertencente à classe NP.
(V) Todos os problemas em NP podém ser reduzidos polinomialmente a um único problema de lógica denominado SAT (Problema de satisfabilidade)
(V) Um problema de decisão Π é NP-Completo se for NP-Árduo e pertencer à NP.
(V) P=NP se e somente se um problema NP-Completo puder ser resolvido por um alg. Determinísico polinomial.
(V) Um problema pertence a classe P dos problemas de decisão se existir algum algoritmo que o resolva em tempo polinomial.
(V) Um problema ╥1 é redutível a um problema ╥2 se, para qualquer instância de ╥1 uma instância de ╥2 poderá ser construída em tempo polinomial tal que resolvendo ╥2 resolvido ╥1 resolve-se implicitamente ╥1.
(V) A redutibilidade de ╥1 a ╥2 implica que ╥1 pode ser considerado caso particular de ╥2. 
(V) Se ╥1 α ╥2 e ╥2 α ╥1, dizemos que os problemas são equivalentes.
(V) A redutibilidade é uma relação transitiva, assim se ╥1 α ╥2 e ╥2 α ╥3, então ╥1 α ╥3.
(V) Um problema de decisão é NP-Árduo se ╥’ é redutível a ╥ qualquer que seja ╥’
(V) Todos os problemas em NP podem ser reduzidos polinomialmente a um único problema de lógica denominado SAT (problema de satisfabilidade).
(V) Um problema de decisão ╥ é NP-completo se for NP-árduo e pertencer a NP.
(V) P = NP sss um problema NP-completo puder ser resolvido por um algoritmo determinístico polinomial.
(V) Reduzindo um problema NP-completo ou NP-árduo conhecido a outro problema de decisão ╥, podemos afirmar a transitividade da redução, que ╥ é NP-árduo. Se ainda ╥ pertencer a NP, teremos ╥ NP-completo.
(V) Seja ╥ NP-completo. Se a existência de um algoritmo pseudopolinomial para ╥ implicar em NP-CO-NP, então ╥ será NP-completo forte.
(F) Suponha que um problema de decisão X qualquer é SIM. Se e somente se a resposta X for NÃO, então X pertence NP.
(F) Se NP != CO-NP. Um problema de decisão ╥ poderá ser NP-completo se for CO-NP-completo simultaneamente.
(V) Se existir um algoritmo polinomial para um problema pertencente NP-completo, então P = NP interseção CO-NP.
(F) Se um problema de decisão X pertence NP-completo é redução de X2, concluímos que X2 é NP-completo.
(V) O complementar ╥ de um problema ╥ em NP pertence a NP.
(F) Se um problema de decisão não tem reconhecimento polinomial, ele não estará em NP.
(F) Um problema de cota inferior exponencial pertence a NP.
(V) Se um problema de decisão ╥1 é redutível a outro problema de decisão ╥2 e ╥2 está na classe P, então ╥1 pertence a P.
(V) Seja m problema NP-completo. O prob. ╥ pertence a P sss P = NP.
(V) Um problema ╥ pertence a classe CO-NP dos problemas de decisão se for exibida uma justificativa a resposta NÃO para que a etapa de reconhecimento seja realizada em tempo polinomial no tamanho da entrada de ╥
(V) Se o complemento de um problema de decisão ╥ é outro problema ╥ tal que a resposta à ╥ é SIM sss a resposta a ╥ for NÃO.
(V) Dizemos que um problema ╥ pertence a classe NP dos problemas de decisão se tivermos um algoritmo não-determinístico polinomial para ╥ 
(V) Reduzindo um problema NP-Completo ou NP-Árduo conhecido a outro problema de decisão Π, podemos afirmar pela transitividade da redução, que Π é NP-Árduo. Se ainda Π pertencer a NP, temos Π NP-Completo.
(V) Seja Π NP-Completo. Se a existência de um alg. Pseudo-polinomial para Π implicar em NP-CO-NP, então Π será NP-Completo forte.
(F) Suponha que um problema de decisão X qualquer é SIM se e somente se resposta X for NÃO então X ∈ NP.
(F) Se NP≠CO-NP, um problema de decisão Π poderá ser NP-Completo se CO-NP-Completo simultaneamente.
(V) Se existir um alg. Polinomial para um problema ∈ NP-Completo então P=NP∩CO-NP.
(F) Se um problema de decisão X ∈ NP-Completo é redução de X2, podemos concluir que X2 é NP-Completo.
(F) Se um problema de decisão NÃO tem reconhecimento polinomial, ele estará em NP.
(F) Um problema de cota inferior Exp. ∈ NP.
(V) Se um problema de decisão Π1 é redutível a outro problema de decisão Π2 e Π2 está na classe P então Π1 pertence a classe P.
(V) Seja Π um problema NP-Completo. O problema Π pertence a P se e somente se P=NP.
(V) Um problema Π pertence a classe CO-NP dos problemas de decisão se for exibida uma justificativa à resposta NÃO para Π, cuja etapa de reconhecimento seja realizada em tempo polinomial no tamanho da entrada de Π.
(V) O complemento de um problema de decisão Π é outro problema Π tal que a resposta a Π é SIM se e somente se a reposta a Π for não.
(V) O complementar Π de um problema Π em NP, pertence a classe NP.
(V)Um problema pertence a classe P dos problemas de decisão se existir algum algoritmo que o resolva em tempo polinomial.
(V)Um problema π1 é redutível a um problema π2 se, para qualquer instância de π1, uma instância de π2 poderá ser
 construída em tempo polinomial tal que resolvendo π2 resolvido π1 resolve-se implicitamente π1.
(V)A redutibilidade de π1 a π2 implica que π1 pode ser considerado caso particular de π2. 
(V)Se π1 α π2 e π2 α π1, dizemos que os problemas são equivalentes.
(V)A redutibilidade é uma relação transitiva, assim se π1 α π2 e π2 α π3, então π1 α π3.
(V)Um problema de decisão é NP-Árduo se π’ é redutível a π qualquer que seja π pertencente a classe NP. 
(V)Todos os problemas em NP podem ser reduzidos polinomialmente a um único problema de lógica denominado SAT (problema de satisfabilidade).
(V)Um problema de decisão π é NP-Completo se for NP-Árduo e pertencer a NP.
(V)P=NP se e somente se um problema NP-Completo puder ser resolvido por um algoritmo determinístico polinomial.
(V)Reduzindo um problema NP-completo ou NP-árduo conhecido a outro problema de decisão π, podemos afirmar a transitividade da redução, que π é NP-árduo. Se ainda π pertencer a NP, teremos π NP-completo.
(V) Seja π NP-completo. Se a existência de um algoritmo pseudopolinomial para π implicar em NP-CO-NP, então π será NP-completo forte. _
(F)Suponha que um problema de decisão X qualquer é SIM. Se e somente se a resposta X for NÃO, então X Є NP.
(F)Se NP ≠ CO-NP. Um problema de decisão π poderá ser NP-completo se for CO-NP-completo simultaneamente.
(V)Se existir um algorítmo polinomial para um problema Є NP-completo, então 
P=NP∩ CO-NP.
(F)Se um problema de decisão X Є NP-completo é redução de X2, concluímos que X2 é NP-completo. _
(V)O complementar π de um problema π em NP pertence a NP.
(F)Se um problema de decisão não tem reconhecimento polinomial, ele não estará em NP.
(F)Um problema de cota inferior exponencial pertence a NP. 
(V)Se um problema de decisão π1 é redutível a outro problema de decisão π2 e π2 está na classe P, então π1 pertence a P.
(V)Seja um problema NP-completo. O prob. π pertence a P se e somente se P=NP. 
(V)Um problema π pertence a classe co-NP dos problemas de decisão se for exibida uma justificativa a resposta ‘ NÃO’ para que a etapa de reconhecimento seja realizada em tempo polinomial no tamanho da entrada de π. _
(V)Se o complemento de um problema_ de decisão π é outro problema π tal que a resposta á π é SIM se e somente se a resposta a π for NÃO.
(V)Dizemos que um problema π pertence a classe NP dos problemas de decisão se tivermos um algoritmo não-determinísticopolinomial para π.