„Samræmingarverkefni Posts“: Munur á milli breytinga

Efni eytt Efni bætt við

Innfellt

Útgáfa síðunnar 12. október 2012 kl. 02:21

Samræmingarverkefni Posts^[1] er óleysanlegt ákvörðunarvandamál sem Emil Post lagði til árið 1946. Vandamálið gengur út á að taka tvo endanlega orðalista $\alpha _{1},\ldots ,\alpha _{N}$ og $\beta _{1},\ldots ,\beta _{N}$ úr einhverju stafrófi $A$ sem inniheldur minnst tvö tákn og skilar röð af vísum $(i_{k})_{1\leq k\leq K}$ þar sem $K\geq 1$ og $1\leq i_{k}\leq N$ fyrir öll $k$ svo að

\alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}.

Tilvísanir

↑ Algorithms, Logic, and Complexity Icelandic-english course dictionary

[1] Algorithms, Logic, and Complexity Icelandic-english course dictionary

[1]

Útgáfa síðunnar 12. október 2012 kl. 02:20 breyta BiT (spjall \| framlög) 15.627 breytingar mEkkert breytingarágrip ← Eldri breyting		Útgáfa síðunnar 12. október 2012 kl. 02:21 breyta taka aftur þessa breytingu BiT (spjall \| framlög) 15.627 breytingar mEkkert breytingarágrip Nýrri breyting →
Lína 1:		Lína 1:
	'''Samræmingarverkefni Posts'''<ref>[https://notendur.hi.is/hh/kennsla/rrr/h06/ordalisti.html Algorithms, Logic, and Complexity] Icelandic-english course dictionary</ref> er [[óleysanlegt vandamál\|óleysanlegt]] [[ákvörðunarvandamál]] sem [[Emil Post]] lagði til árið [[1946]]. Vandamálið gengur út á að taka tvo endanlega orðalista <math>\alpha_{1}, \ldots, \alpha_{N}</math> og <math>\beta_{1}, \ldots, \beta_{N}</math> úr einhverju stafrófi <math>A</math> sem inniheldur minnst tvö tákn og skilar röð af [[vísir\|vísum]] <math>(i_k)_{1 \le k \le K}</math> þar sem <math>K \ge 1</math> s <math> 1 \le i_k \le N</math> fyrir öll <math>k</math> svo að		'''Samræmingarverkefni Posts'''<ref>[https://notendur.hi.is/hh/kennsla/rrr/h06/ordalisti.html Algorithms, Logic, and Complexity] Icelandic-english course dictionary</ref> er [[óleysanlegt vandamál\|óleysanlegt]] [[ákvörðunarvandamál]] sem [[Emil Post]] lagði til árið [[1946]]. Vandamálið gengur út á að taka tvo endanlega orðalista <math>\alpha_{1}, \ldots, \alpha_{N}</math> og <math>\beta_{1}, \ldots, \beta_{N}</math> úr einhverju stafrófi <math>A</math> sem inniheldur minnst tvö tákn og skilar röð af [[vísir\|vísum]] <math>(i_k)_{1 \le k \le K}</math> þar sem <math>K \ge 1</math> og <math> 1 \le i_k \le N</math> fyrir öll <math>k</math> svo að

	: <math>\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}.</math>		: <math>\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}.</math>