2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 4, 5, 6, 7, 8
 
 Re: P vs NP .
Сообщение06.04.2019, 19:16 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Ioda в сообщении #1386308 писал(а):
то выберу это
Это - это какое?

Я правильно понимаю, что вы хотите ввести функцию $f(x)$, равную минимуму $t(M, x)$ по всем МТ $M$, работающим полиномиальное время и распознающих некоторый язык (автоматически из $P$), содержащий $x$?
Тогда $f(x) = 1$, т.к. есть язык $L$, состоящий из всех слов, и МТ $M$, распознающая его за один такт.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение06.04.2019, 19:24 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1386315 писал(а):
Я правильно понимаю, что вы хотите ввести функцию $f(x)$, равную минимуму $t(M, x)$ по всем МТ $M$, работающим полиномиальное время и распознающих некоторый язык (автоматически из $P$), содержащий $x$?

Нет-нет. Я имел ввиду ,что такое выражение я выберу временем распознавания некоторого слова лежащего в пересечении языков ,для остальных все обыкновенно.
mihaild в сообщении #1386315 писал(а):
Это - это какое?

Это ,то которое про биекцию между $X$ и $P$ в виде $\operatorname{pr_1}$ .

 Профиль  
                  
 
 Re: P vs NP .
Сообщение06.04.2019, 19:35 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Ioda в сообщении #1386316 писал(а):
Я имел ввиду ,что такое выражение я выберу временем распознавания некоторого слова лежащего в пересечении языков ,для остальных все обыкновенно.
Расшифруйте. Пока что я понял, что вы для каждого языка $L$ из $P$ выбрали МТ $M(L)$, распознающую этот язык за полиномиальное время. Так?
Дальше вы вроде бы хотите для каждого слова взять какое-то время. Какое?

 Профиль  
                  
 
 Re: P vs NP .
Сообщение06.04.2019, 19:47 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1386319 писал(а):
Расшифруйте.

Вот :
mihaild в сообщении #1386319 писал(а):
Пока что я понял, что вы для каждого языка $L$ из $P$ выбрали МТ $M(L)$, распознающую этот язык за полиномиальное время.

mihaild в сообщении #1386319 писал(а):
Дальше вы вроде бы хотите для каждого слова взять какое-то время. Какое?

Да. Я могу потребовать непересечение языков?
Если нет ,то если слово $x$ принадлежит лишь одному языку $L$ ,то время распознавания для данного слова есть $t(M(L),x)$ . Если слово $x$ принадлежит пересечению некоторого множества языков $\{L_1,\dots ,L_n\}$ ,то время его распознавания определим ,как $\min\limits_{}(t(M_1(L_1),x),\dots ,t(M_n(L_n),x))$ .

 Профиль  
                  
 
 Re: P vs NP .
Сообщение06.04.2019, 20:15 


14/01/11
2916
Ioda в сообщении #1386322 писал(а):
время его распознавания определим ,как $\min\limits_{}(t(M_1(L_1),x),\dots ,t(M_n(L_n),x))$ .

И как вы собираетесь добиться такого времени? Может, для $n$-ленточной МТ это и было бы справедливо, но ведь эмуляция многоленточной МТ посредством одноленточной, очевидно, несёт определённые издержки.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение06.04.2019, 20:29 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Ioda в сообщении #1386322 писал(а):
Я могу потребовать непересечение языков?
Вы можете потребовать что угодно, но нужно явно выписать список требований. И потом показать, что объект, удовлетворяющий требованиям, существует.
Например так: нам нужно множество пар вида (что-то, язык из $P$), такое что:
1. Любой язык из $P$ является вторым элементом ровно одной пары.
2. Никакие два вторых элемента разных пар не пересекаются.
Очевидно, что множества, удовлетворяющего обоим этим свойствам, не существует.
Ioda в сообщении #1386322 писал(а):
,то время его распознавания определим ,как $\min\limits_{}(t(M_1(L_1),x),\dots ,t(M_n(L_n),x))$
Только давайте эту функцию назовем как-то иначе - уже есть функция $t(M, x)$, так называющася.
Хорошо, сойдет (только ваша запись подразумевает что множество языков, которым принадлежит $x$, конечно, что не так).
Итого формально мы по функции $M$ построили функцию на словах: $f(x) = \min\limits_{L \in P: x \in L} t(M(L), x)$. Так?
Давайте опять для простоты возьмем какую-нибудь более конкретную функцию $M$. Например возьмем язык $U$, состоящий из вообще всех слов, и скажем что $M(U)$ - МТ, которая просто останавливается за 1 такт с ответом "да". Тогда $f(x) \equiv 1$. Что дальше?

(Оффтоп)

Sender в сообщении #1386324 писал(а):
И как вы собираетесь добиться такого времени?
Да там просто какая-то функция, никакого отношения к $P$ не имеющая. Тут товарищ пытается найти какие-то закономерности в словах, принадлежащих языкам из $P$.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение06.04.2019, 21:04 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1386325 писал(а):
Итого формально мы по функции $M$ построили функцию на словах: $f(x) = \min\limits_{L \in P: x \in L} t(M(L), x)$. Так?

Да. Хотя ,кажется я понял к чему вы клоните ,поэтому давайте не так определим . Давайте так :
$$f(x)=\lim\limits_{n\to\infty}^{}\sum\limits_{x\in \bigcap\limits_{i=1}^{n}L_i ,L_i\in P}^{}\frac{t(M_i(L_i),x)}{n}$$
Согласны ?

(Оффтоп)

mihaild в сообщении #1386325 писал(а):
Тут товарищ занимается совершенно безнадежным делом

Ну почему ? Отыщем ошибку ,хотя бы одному из нас точно станет легче.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение06.04.2019, 21:18 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Ioda в сообщении #1386326 писал(а):
Давайте так :
$$f(x)=\lim\limits_{n\to\infty}^{}\sum\limits_{x\in \bigcap\limits_{i=1}^{n}L_i ,L_i\in P}^{}\frac{t(M_i(L_i),x)}{n}$$
Согласны ?
Да вы можете заводить любую функцию какую хотите. Правда в этом случае вам нужно показать существование предела. И как минимум для некоторых упорядочений $P$ и функций $M$ этот предел не существует, а для некоторых равен $\infty$. И вроде бы таким способом можно получить вообще любую функцию $\{0, 1\}^* \to [1; \infty)$.

UPD: почитал внимательнее, всё-таки там невнятная сумма какая-то. Видимо под пределом должно быть $\frac{\sum_{L_i: i \leqslant n, x \in L_i} t(M(L_i), x)}{\left|\{L_i: i \leqslant n, x \in L_i\}\right|}$. И если вы под $M_i(L_i)$ имели в виду $M(L_i)$, то внешний индекс не нужен, а если вы теперь вводите несколько функций от языков - то напишите, какие.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 113 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group