Preguntas de computational-complexity04

24

1Resp

5426Vistas

Las pruebas de la factorización entera están en $P$

Resuelta

Preguntado el 28 de Octubre, 2011 por dwelch

1

2Resp

168Vistas

Ayuda para la función Möbius

Resuelta

Preguntado el 23 de Noviembre, 2012 por jasimmk

3

1Resp

458Vistas

Toda TM no determinista tiene una TM determinista equivalente.

Resuelta

Preguntado el 25 de Febrero, 2018 por Smart

23

2Resp

1409Vistas

¿Cuál es la complejidad de este problema?

Resuelta

Preguntado el 9 de Julio, 2011 por bneely

3

1Resp

284Vistas

Límite superior de complejidad de los circuitos de fórmulas booleanas más difíciles

Resuelta

Preguntado el 28 de Octubre, 2015 por Jsevillamol

24

4Resp

4040Vistas

Límites inferiores de complejidad temporal superlineal para cualquier problema natural en NP?

Resuelta

Preguntado el 11 de Noviembre, 2009 por Aidan Ryan

1

1Resp

1432Vistas

crack RSA: ¿NP o NP-completo?

Resuelta

Preguntado el 16 de Agosto, 2011 por axk

2

1Resp

2109Vistas

Demuestre lo siguiente: si $f(n)$ es $O(g(n))$ y $g(n)$ es $O(h(n))$ entonces $f(n)$ es $O(h(n))$

Resuelta

Preguntado el 11 de Diciembre, 2011 por Simulant

2

3Resp

84Vistas

¿Cuál es el mejor software de cálculo (gratuito/barato)?

Resuelta

Preguntado el 7 de Julio, 2020 por Tim Crosby

6

1Resp

1248Vistas

¿cuál es la relación entre la clase de complejidad E(y EXP) y NP?

Resuelta

Preguntado el 15 de Febrero, 2012 por Form

2

1Resp

389Vistas

Búsqueda eficiente de un ciclo de 5 en un grafo disperso.

Resuelta

Preguntado el 14 de Diciembre, 2010 por Dylan

21

5Resp

4093Vistas

¿Por qué la relativización no puede resolver NP !=P?

Resuelta

Preguntado el 15 de Agosto, 2010 por Chris Driver

20

3Resp

5717Vistas

Satisfacción de fórmulas booleanas generales con un máximo de dos ocurrencias por variable

Resuelta

Preguntado el 21 de Diciembre, 2009 por Philipp Keller

3

2Resp

207Vistas

Determinación de la racionalidad y cálculo de una parametrización racional

Resuelta

Preguntado el 11 de Julio, 2012 por anjanb

5

2Resp

2296Vistas

¿Cree que P=NP?

Resuelta

Preguntado el 15 de Abril, 2011 por puetzk

1

2Resp

200Vistas

Pequeña notación oh

Resuelta

Preguntado el 15 de Enero, 2018 por Lene Coenen

19

3Resp

1452Vistas

Una generalización del problema de recuento de triángulos para grafos ponderados simples

Resuelta

Preguntado el 10 de Agosto, 2012 por Roddy

1

2Resp

113Vistas

Diseñar un autómata finito comprobando la división del número de caracteres

Resuelta

Preguntado el 9 de Enero, 2016 por timedistance

1

1Resp

83Vistas

Análisis de la complejidad de los logaritmos

Resuelta

Preguntado el 26 de Febrero, 2013 por bigO

1

1Resp

319Vistas

Funciones de emparejamiento eficaces

Resuelta

Preguntado el 10 de Junio, 2018 por casperOne

18

12Resp

4191Vistas

Límites inferiores en informática teórica

Resuelta

Preguntado el 11 de Julio, 2010 por Mike B

4

2Resp

84Vistas

Complejidad del cálculo del radio espectral de una matriz cuadrada no simétrica

Resuelta

Preguntado el 28 de Febrero, 2021 por DFK

1

1Resp

46Vistas

Máximo de la suma ponderada de exponenciales

Abierta

Preguntado el 20 de Enero, 2021 por Justin Giboney

47

20Resp

12935Vistas

¿Qué te dice realmente Big O?

Resuelta

Preguntado el 16 de Septiembre, 2021 por Christopher Hitchens

2

1Resp

554Vistas

Problema de Empaquetamiento de Bins con tamaño fijo de bins

Resuelta

Preguntado el 27 de Agosto, 2020 por Pur2all

9

2Resp

859Vistas

¿Producto de sumas de todos los subconjuntos módulo $k$?

Resuelta

Preguntado el 15 de Enero, 2018 por Marek Wolny

37

1Resp

1022Vistas

¿Se puede comprobar más rápido alguna prueba de que $\det(A) \ne 0$ que la multiplicación de matrices?

Resuelta

Preguntado el 25 de Febrero, 2018 por Misha

15

3Resp

27870Vistas

Complejidad temporal de la descomposición LU

Resuelta

Preguntado el 18 de Junio, 2015 por hayer

7

1Resp

124Vistas

Metric TSP con costo de arista entero

Resuelta

Preguntado el 10 de Julio, 2021 por Carlos Barbosa

3

1Resp

241Vistas

Prueba de conocimiento cero - Información sin conexión

Cerrada

Preguntado el 8 de Agosto, 2017 por Lewis Barber

Preguntas de computational-complexity

Cualquiera puede hacer una pregunta

Cualquiera puede responder

Se votan las mejores respuestas.

Las pruebas de la factorización entera están en $P$

Ayuda para la función Möbius

Toda TM no determinista tiene una TM determinista equivalente.

¿Cuál es la complejidad de este problema?

Límite superior de complejidad de los circuitos de fórmulas booleanas más difíciles

Límites inferiores de complejidad temporal superlineal para cualquier problema natural en NP?

crack RSA: ¿NP o NP-completo?

Demuestre lo siguiente: si $f(n)$ es $O(g(n))$ y $g(n)$ es $O(h(n))$ entonces $f(n)$ es $O(h(n))$

¿Cuál es el mejor software de cálculo (gratuito/barato)?

¿cuál es la relación entre la clase de complejidad E(y EXP) y NP?

Búsqueda eficiente de un ciclo de 5 en un grafo disperso.

¿Por qué la relativización no puede resolver NP !=P?

Satisfacción de fórmulas booleanas generales con un máximo de dos ocurrencias por variable

Determinación de la racionalidad y cálculo de una parametrización racional

¿Cree que P=NP?

Pequeña notación oh

Una generalización del problema de recuento de triángulos para grafos ponderados simples

Diseñar un autómata finito comprobando la división del número de caracteres

Análisis de la complejidad de los logaritmos

Funciones de emparejamiento eficaces

Límites inferiores en informática teórica

Complejidad del cálculo del radio espectral de una matriz cuadrada no simétrica

Máximo de la suma ponderada de exponenciales

¿Qué te dice realmente Big O?

Problema de Empaquetamiento de Bins con tamaño fijo de bins

¿Producto de sumas de todos los subconjuntos módulo $k$?

¿Se puede comprobar más rápido alguna prueba de que $\det(A) \ne 0$ que la multiplicación de matrices?

Complejidad temporal de la descomposición LU

Metric TSP con costo de arista entero

Prueba de conocimiento cero - Información sin conexión

Etiquetas mas usadas

i-Ciencias.com

Powered by: