Složitost II

Ahoj!
Nenašel by se tady náhodou někdo, kdo chodil na přednášky a byl by ochotnej naskenovat nebo nafotit svoje poznámky z 30. dubna? Bohužel jsem tehdy vynechal a tyhle důkazy už ve Strojilovi chybí. Jedná se přibližně o slajdy 32-35. Případně kdyby někdo měl zájem, můžu do studnice hodit i některý svoje poznámky.
Díky

Cau!

Bohuzel jsem na prednasky nechodil, ucim se taky z materialu ze studnice. Myslim, ze je to celkem kompatibilni s letoskem krome toho konce, takze bych taky rad uvital nejake poznamky z 23. a 30. dubna... Kdyby se nekdo nasel, hodte to prosim do studnice, diky.

Zacal jsem se koukat na ty zkouskove priklady z wiki a modreho a narazil jsem na par problemu...
napr.

NSPACE(n)   vs.   NSPACE(log(n) * n)

ve vysledcich sem nasel jednou ostrou a podruhe neostrou podmnozinu, ale dokazene to nebylo nikde. Neostra podmnozina je jednoducha, viz trivialni vztahy pro NSPACE. Ale ostrou nevim jak dokazat (? pouzit nejak vetu o neterministicke hierarchii?), tak kdyby nekdo vedel poradit, tak bych byl vdecny ;)

Zápisky z těch dvou přednášek jsem dal sem,
moje poznámky to nejsou, tak nevím jestli tam je vše co se na těch dvou přednáškách dělalo.

Díky moc. Já jsem do studnice přidal zápisky ze všech přednášek, který se ještě zkouší a už je nejde najít ve Strojilovi (kromě té z 30. dubna). Kdyby se někomu chtělo a doplnil by ji tam, bylo by to super. Za ty poznámky, co sem přidal langosh, jsem sice rád, ale přece jenom nejsou na některejch místech úplně čitelný :)

Borek wrote:...problemu...

NSPACE(n)   vs.   NSPACE(log(n) * n)

Ako sam pises, neostra inkluzia je trivialna. Co sa tyka ostrej, tak sa podla mna jedna presne o dosledok Translacneho lemmatu (na Kucerovych slajdoch je to slajd 27) - je to tam sice s DTIME, ale vid. poznamka o slajd vyssie, ze transakcne lema sa da dokazat pre DTIME aj DSPACE aj NTIME, takze to funguje aj pre NSPACE.

Cau!

gejza wrote:

Borek wrote:...problemu...

NSPACE(n)   vs.   NSPACE(log(n) * n)

Ako sam pises, neostra inkluzia je trivialna. Co sa tyka ostrej, tak sa podla mna jedna presne o dosledok Translacneho lemmatu (na Kucerovych slajdoch je to slajd 27) - je to tam sice s DTIME, ale vid. poznamka o slajd vyssie, ze transakcne lema sa da dokazat pre DTIME aj DSPACE aj NTIME, takze to funguje aj pre NSPACE.

Kucera asi predelaval slajdy, takze tedka je na strane 27 je polynomialni hierarchie... Mozna je i Tvoje reseni dobre, ale ja jsem tedka pri cteni slajdu nasel na strane 35 dusledek vztahu NSPACE(S(n)) = co-NSPACE(S(n)):

Důsledek: Věta o deterministické prostorové hierarchii platí i pro nedeterministický prostor.

cimz mame ostrou nerovnost primo dokazanou (predpoklady vety jsou snad splneny).

btw. nevite nekdo psl nahodou, jestli jsou nejake pozadavky k ustni? Te teorie je nejak moc, takze co by melo stacit na "splneni" zkousky ;) dik

Ted jsem prochazel slajdy a u Vety o vztazich mezi tridami se body c) a d) dost odlisujou (i kdyz baj voko to rika totez), .. dokazovalo se to stejne, nebo jinak?

To myslíš jako rozdíl od skript?
To d. stejně, v těch slajdech je jenom ta nejsilnější podmínka, víš, že NTIME i DSPACE je pod NSPACE (viz a. a c.), je to tam myslim jako c'.
To c. je asi horší, teď tam nevidim že by to plynulo z těch vět ve skriptech, ale je vidět, že pokud platí to v těch slajdech, tak platí i všechny ty ve skriptech (je to silnější podmínka).
Ono to máš jedno jak se to dokazovalo, podle mě mu tam stačí napsat ten důkaz co je ve skriptech a nějak to převýst.

No taky si to myslim, ale radsi bych videl dokazany to jeho zneni;)

Nechce se mi zakladat novy vlakno. :) Takze dnesni (12.6.) pisemka:

-priklady byly pomerne jednoduche, u 2 vztahu nebylo nic, velka vetsina inkluzi byla ostra

-teoreticka otazka: Borodinova veta ... takze super, sice pomerne tezsi, ale umel jsem to, takze na nic vic se uz neptal.

Nevíte někdo náhodou, jestli některé důkazy Čepek NEZKOUŠÍ?

Pokud se dobře pamatuju, tak například u věty o redukci počtu pásek pro časovou složitost se na přednášce asi na 20 minut úplně zamotal a následně prohlásil, že to ani nezkouší, protože i on sám to bez svých papírů nedává... A vypadalo to že má na mysli všechny věty z těch několika úvodních "technických" přednášek. Takže, je to pravda? Dostal jste někdo konkrétně tuhle větu? Učíte se všechno nebo jen něco?

Nevim jak to je s tim, jestli se něco nezkouší, ale já z osobní zkušenosti můžu říct, že se zkouší i alternující/omezené kvantifikátory... Je tam spousta definic a vět, takže u tý otázky stačí spíš všechno sepsat a vědět o čem to je, než něco dokazovat. Ale i tak, celkem překvapivá otázka si myslim.

Vety zo začiatku sa neskúšajú (redukcia počtu pások na jednu, priestorová kompresia a časová kompresia). Nemalo by to význam, keďže v nich nie je žiadna myšlienka a je to len nepohodlné technické hranie sa (viď napríklad práve priestorovú kompresiu).

Dnešní písemka:

-příklady jsou na wiki (termín 2002-06-21)

-otázku jsem dostal translační lemma a větu o nedeterministické prostorové hierarchii, dále jsem zaslechl větu o časové hierarchii... prostě klasika

celkově pohodová zkouška, odcházel jsem ani ne za hodinu a čtvrt (i s písemkou) s jedničkou...

Malý hint na závěr: pokud víte že máte písemku dobře, udělejte u nějaké inkluze drobnou chybu. Čepek vám pak sice strhne půl bodu až bod, ale pak se vás zeptá na větu, která se tam používala. Takže pokud nějakou větu chcete přímo dostat, tohle je velice elegantní způsob jak to zařídit. Samozřejmě bez záruky, ale dnes to fungovalo snad u všech zůčastněných. :)

Jak jsem si dnes mohl na vlastní kůži ověřit, tak se zkouší i věci, co se dělají na cvikách a nejsou ve slajdech, což je podle mě prima, protože je to jednodušší než mnohé důkazy, co se dělaly na přednášce. Ale trochu mě to překvapilo:). Měl jsem (1) PSPACE-úplný problém a dokázat aspoň, že je v PSPACE, a pak (2) co by se stalo, kdyby nějaký $A \in \Sigma_k$ byl PSPACE-úplný. Když jsem dostal tu první otázku, tak jsem si říkal, sakra, kde to v tý přednášce bylo… a pak jsem sám sebe překvapil, co všechno si pamatuju z cvik. Možná ještě štěstí, že jsme to dělali zrovna na těch posledních.

Ahoj,
nemohl by sem někdo dát příklady, které se dělaly na cvičení?

THX-1138 wrote:Ahoj,
nemohl by sem někdo dát příklady, které se dělaly na cvičení?

Prosím? :)

Bohužel nevím, co se tam dělalo, ale přednášející říkal, že to, co bylo na cvičeních, zkoušet nebude - že to bylo navíc.

Ahoj,

mam za sebou zkousku, takze prubeh je stale stejny, nejprve "prakticka cast" (viz wiki, dokonce myslim, ze jsme dostali jednu z pisemek tam napsanych, ale bez zaruky:)) a pak si losujete otazku. Soude dle delky seznamu (mel ho psany rukou takze sem moc neprecetl) tam ma asi 20 otazek, takze bych rekl, ze se pta uplne na vsechno - jinak ja mel stesti - prevod k-paskoveho na 1 paskovy, za mnou bylo translacni lemma, zbytek otazek jsem bohuzel neslysel (treba je nekdo prida). Na postup je treba 7/10 ale udelali to vsichni a myslim, ze pokud tam nenapisete uplny kraviny tak vas nevyhodi. Celkove je strasne hodnej, bohuzel ma otazka jaksi byla prilis jednoducha na to, abych zjistil jak moc chce jit do hloubky atp. - jedine co, ze u me nechtel konstruovat primo ten stroj, coz jsem ale stejne udelal:)).

Takze hodne zdaru u zkousky

Ahoj, kdo jste uz bylli letos na slozitosti II - chapu to spravne, ze zapocet a zkouska se dela najednou? Z Cepkovo stranky to na me pusobi, jako by se delalo kazde zvlast, stejne jako u slozitosti I.

Kubees wrote:Ahoj, kdo jste uz bylli letos na slozitosti II - chapu to spravne, ze zapocet a zkouska se dela najednou? Z Cepkovo stranky to na me pusobi, jako by se delalo kazde zvlast, stejne jako u slozitosti I.

Ahoj, na zkousce jsem jeste nebyl, ale presne na tohle jsem se ho ptal na posledni prednasce. Rikal, ze to na webu opravi. Situace je opravdu takova, ze prakticka i teoreticka cast je najednou (postupne, samozrejme :) ).

Diky. :wink:

A jeste jedna otazka: Existuje nejaky seznam casto kladenych teoretickych otazek? Proc tady na foru do haje nic neni?! :D Lidi nebudte lini a napiste sem na co se vas ptal, diky. :)

Kubees wrote:A jeste jedna otazka: Existuje nejaky seznam casto kladenych teoretickych otazek? Proc tady na foru do haje nic neni?! :D Lidi nebudte lini a napiste sem na co se vas ptal, diky. :)

Nejspíš všechny věty u kterých neříkal, že je nezkouší... tipnul bych si, že bude preferovat věty ze slajdů 12-14 (ono většina jiných slajdů jsou definice :-), ale neručím za to...
Já dostal VoDPH... na to že jsem se na zkoušku učil půl noci a tenhle důkaz se vůbec neučil a jen ho prolétl abych alespoň trochu tušil, takže jsem téměř celý důkaz vymýšlel, to dopadlo velice dobře (1)... Když člověku něco chybí, ale většinu už má, tak to s ním projde, nechá doplnit chybějící... pokud člověk doplní něco špatně a není to hned potřeba, tak jde dál a nechá člověku čas si uvědomit, že vlastně řekl blbost a opravit to, nepočítá to rovnou jako mínus... občas i něco poradí.
Akorát je dobré odevzdávat tu zápočtovou písemku mezi prvními - bral cca. po třech (tři jsme šli hned a tři měli přijít odhadem za hodinu, hodinu a půl).

Zřejmě poslední moje zkouška na MFF :) Písemku jsem měl napsanou z minulého termínu, kde jsem nešel na ústní, a měl jsem asi mínus 1,5 bodu. Dneska jsem dostal PH definovat pomocí alt. kvantifikátorů a k tomu napsat nějaké vztahy. Tohle jsem při učení nejak vypustil, takže jsem měl temno. Dostal jsem tedy náhradní otázku, která se mi naopak dost líbila. Nedeterministická prostor. hierarchie pro polynomy. U důkazu jsem neměl zdůvodněné ty zřetězené inkluze(proč platí), tak mě to nechal dopsat a pak jsem odešel s trojkou(vzhledem k né úplně super písemce a té PH), což mi prostě stačilo. Kolega, který byl se mnou a taky měl písemku z minula, dostal PH definovat pomocí orákulových strojů a k tomu vztah PH a PSPACE. Uměl to na 1-2 a dostal nabídku znovu si napsat písemku, aby mohl dostat jedničku. Nabídku přijal, ale jak dopadl už nevím.
GL všem, které to ještě čeká.

Zde je pár přednášek a mezi nimi jedno cvičení nahrané na diktafon. Když nebudu líný, tak ještě přidám naskenované poznámky, aby to bylo trochu k něčemu.
http://www.uloz.to/xSkbVmD/slozitostii-rar

Andreas wrote:Když nebudu líný, tak ještě přidám naskenované poznámky, aby to bylo trochu k něčemu.
http://www.uloz.to/xSkbVmD/slozitostii-rar

to by som bol povdacny, a mozno aj ostatni, co to este nedali...
dik za tie nahravky. :-)

Nevite o nejakem zdroji, ze kterho by se daly naucit ty vety a dukazy, ktere chybi ve Strojilovi?

Konkretne mam na mysli definice PH Pomoci orakul/alternujicich kvantifikatoru + vztahy okolo, ta veta ze existuje NP problem ktery neni P ani NP-uplny, vztah NTIME <= DSPACE, a mozna jeste nejake dalsi....

Ono je totiz docela blbe, kdyz se clovek krasne nauci dukazy ze Strojila a pak vyleti na dukazu ktery tam chybi :D (uz 2x)

Kubees wrote:Nevite o nejakem zdroji, ze kterho by se daly naucit ty vety a dukazy, ktere chybi ve Strojilovi?

Treba Veta o vztazich je na wiki.matfyz.info . Def. PH pres alt. kvant. je v nejakych poznamkach na Studnici. Myslim, ze to pujde +- vsechno poskladat.

Ale mas pravdu, asi neni dostupne nic, kde by to bylo komplet pohromade. Nahral jsem teda do Studince (zatim v INCOMING/Slozitost II/poznamky/peci1) svoje 4strankove vypisky. Je tam uplne vsechno, jen to mozna neni obcas moc k precteni, nemam zrovna vystavni pismo =)

Ahoj, pridavam svuj minireport ze zkousky. Tridy slozitosti si nepamatuju, akorat jedna mi uvizla v hlave. Bylo to neco jako DSPACE(n) a DTIME(2^(n*log n)). Pres Vetu o vztazich jsem jednoduse odvodil neostrou nerovnost, ale da se i ostra! A to tak, ze ten DS(n) ostre vlozite treba do DS(n * loglog n).

Moje otazka byla veta o determ. cas. hierarchii. Dukaz zkoumal docela dukladne, takze urcite nestaci jenom povrchni znalost (teda, asi staci na 2 nebo 3, ale ne na 1 :) ). A jako doplnek se me zeptal na zneni Ladnerovy vety (tj. mam pocit snad uplne posledni prednaska).

Neni treba se Cepka bat, je hodnej (ale ferovej :) ).

Třídy složitosti byly v pohodě. Jen je dobré nezapomenout (jako já), že jde používat i "jednoduché" věty (lineární zrychlení).

Větší část otázky byla Borodinova věta - lemmata stačilo zformulovat. Pak následovaly definice prostorové konstruovatelnosti & vyčíslitelnosti v lineárním čase a idea důkazu ekvivalence.

Obecně mi styl zkoušení přišel "hodný, pokud do toho člověk trochu vidí" - tj. pokud jsem se třeba přeřekl (že jsem řekl lineární zrychlení místo lineární prostorové komprese atd.), nic se nedělo. Ale jinak pan Čepek docela důkaz zkoumá, není to styl Pultr/Kučera, u kterých vcelku stačí na papír +- načmárat ideu.

Jinak se asi docela potvrzuje ten algoritmus na zisk otázky na nějakou hierarchii :)

Tak ja uz to mam konecne taky uspesne za sebou. Mas pravdu, ze ty chybejici dukazy se daji najit v naskenovanych poznamkach, a diky bohu za to, protoze jsem dostal opet dukaz PH <= PSPACE, na kterym jsem den predtim vyletel, ovsem tentokrat jsem byl pripraven => 1 :D Jako doplnujici otazku jsem jeste dostal dukaz, ze NTIME <= DSPACE - uz jen v rychlosti nacrtnout. Cepek zrejme s oblibou dava stejnou otazku, ktera vas zabila u predchoziho terminu (pokud si zapamatuje vas ksicht), kolegovi vedle udelal totez s alternujicimi kvnatifikatory.

Jinak nejbeznejsi otazky co jsem zaslechl - tyhle tam tocil neustale na vsech 3 terminech co jsem byl (ale nejen ty):

• nedet. pros. hierarchie

• veta o vztazich (verze NTIME <= DSPACE a verze exponencialni strceni NSPACE do DTIME)

• translacni lemma

• definice PH pomoci orakul a PH <= PSAPCE

• definice PH pomoci alt. kvant. + nejaky dukaz ale nevim ceho

Co se tyce pisemky: kdyz se clovek nauci princip, ktery neni tezky, tak uz je to brnkacka. Staci umet Vety o hierarchii a o vztazich a Savicovu vetu. (ktere stejne musite umet na ustni :) )

Pokud by mel nekdo zajem tak prihazuju skeny 2 mych vstupnich testu, je tam jen jedna drobna chyba, jinak jsou ok. Zajimave je mozna to, ze proslo ze NSPACE(n) je neostra podmnozina NSPACE(n log n), coz se resilo na zacatku tohoto vlakna.

Attachments:

• P6230005.JPG

• P6230004.JPG

Písemka stejná jako příspěvek přede mnou. Doporučuju si pořádně přečíst zdůvodnění k bodu 3: poslední inkluze ve zdůvodnění je neostrá, měl jsem ji jako ostrou a hned to vygeneruje 4 chyby (a přišlo mi, že to byla častá chyba). Každopádně Čepek počítal stejné chyby jako jednu chybu takže zápočet dostali i ti se 4 chybami (tolerovány jsou normálně 3).

(Zdůvodnění proč nemůže být inkluze ostrá je jako kdybych měl otevřený interval (0, e) kde e <1 a (0,e) < (0,1) (tady je ostrá pro každé e). Ale nekonečné sjednocení těchto intervalů U (0,e) <= (0,1) už může být i interval (0,1). A v tom zdůvodnění se sjednocuje přes všechny ty konstanty. Tak nějak to vysvětloval Čepek, snad jsem to nezkazil).

A jako důsledek písemky jsem dostal větu o vztazích, část b. Tady v důkazu pozor, že hrany v tom grafu jsou ohodnoceny vstupními symboly aby se poznalo kdy ten stroj má přijímat (ptal se kdy ten DTS který vyrobím bude přijímat). Jinak zkoušení mírné, myšlenka důkazu mu stačila i když jsem tam měl často špatné výpočty a někde blbosti. Výsledek za 2.

A slyšel jsem otázku QBF je PSPACE úplný (ale tuším že to byla druhá otázka - záchranná).

Prijde mi, ze Slozitost II forum i wiki jsou na slozitostni zkousky ponekud skoupe, pojdme to vylepsit.

[24.6.2014] Pisemka pro ziskani zapoctu mela stejny prubeh jako drive.

• zadano 5 slozitostnich trid

• pro vsech 10 dvojic ukazat, zda existuje inkluze a pokud existuje, zda je ostra

Pozor! Odpoved muze byt, ze pro danou dvojici nemame patricny aparat, kterym muzeme vztah dokazat.
Napr. na obrazcich pisemek zde na foru jsou vztahy takovych trid oznaceny otazniky.
Vetsinou jsou v pisemce tak 3 z 10 takove, o kterych neumime rozhodnout.
Skutecne tam staci dat otaznik.

Bacha! Nesnazte se dokazat, ze inkluze neplati. Vetsinou ten vztah plati, ale patricny aparat se neprednasi.
Dnesni pisemka [nadepsana cislo 4] byla skutecne stejna jako ta druha zde na foru.

Na cvicenich se loni delaly tyto tridy:
$$DTIME(2^{n^2}), DSPACE(n^2),DSPACE(n\log(n)),NTIME(n\log(n)),NSPACE(\sqrt(n)\log(n))$$

$1. DSPACE (n \log(n))$ ve vztahu k: $DSPACE(n^2)$
$2. DSPACE (n \log(n))$ ve vztahu k: $DTIME(2^{n^2})$
$3. DSPACE (n \log(n))$ ve vztahu k: $NSPACE(\sqrt(n)\log(n))$
$4. DSPACE (n \log(n))$ ve vztahu k: $NTIME(n\log(n))$
$5. DSPACE(n^2)$ ve vztahu k: $DTIME(2^{n^2})$
$6. DSPACE(n^2)$ ve vztahu k: $NSPACE(\sqrt(n)\log(n))$
$7. DSPACE(n^2)$ ve vztahu k: $NTIME(n\log(n))$
$8. DTIME(2^{n^2})$ ve vztahu k: $NSPACE(\sqrt(n)\log(n))$
$9. DTIME(2^{n^2})$ ve vztahu k: $NTIME(n\log(n))$
$10.NSPACE(\sqrt(n)\log(n))$ ve vztahu k: $NTIME(n\log(n))$

A jako bonus jedno odposlechnute zkouskove zadani: **Dokazte mi, ze se cela polynomialni hierarchie vleze do PSPACE. **
[btw. hezky obrazek PH je na Wiki http://en.wikipedia.org/wiki/Polynomial_hierarchy ]

Spravne odpovedi: $\subsetneqq, \subsetneqq, ? , \supseteq, ?, \supsetneqq, \supsetneqq, \supsetneqq, \supsetneqq, ?$
[Otaznik znaci: nedovedeme rozhodnout].

Pozorovani:
Ve 3 pripadech ze 3 [co jsou na foru] melo zadani tvaru:
[N|D]SPACE(vyraz) se tridou DTIME(2^vyraz), odpoved "?" [tj. nedovedeme rozhodnout]

Zápočet 24.6. 2014: byl klasický, byly tam nějaké $\log_3$, ale nic, čím bychom se měli nechat zastrašit. Písemka byla stejná, jako druhá z ofocených, které jsou na předchozí stránce. Myslím, že nikdo neměl výraznější problémy, Čepek nepopotahoval za drobné chyby a bral to rozumě. Pozor ale na korektní použití věty o Vztazích, pár lidem vytknul, že ji používají špatně (musí se zrychlovat/odhadovat každý jazyk zvlášť!).

Zkouška 26.6. 2014: Dorazili jsme na 8:30 a zápočet měli zapsaný, Čepek rozdal písemky a pak nám pověděl témata. Někomu co neuměl na písemce, někomu něco jiného, jak kdy. Já jsem dostal zadefinovat $PH$ přes orákula a dokázat, že $PH \subseteq PSPACE$. Tak jsem zadefinoval, trošku neformálně, včetně důkazu. Na pár formalit se mě zeptal (jak je definované to odvozování tříd a proč lze nahradit tázání orákula za orákulum -- protože tázací páska se počítá do složitosti), a dal mi jedničku (ačkoliv jsem měl zápočet "s odřenýma ušima").

Dále jsem slyšel: deterministickou hierarchii (myslím, že časovou), QBF je PSPACE-úplný a Borodinovo větu (!). Jako doplňující otázka padaly části věty o vztazích.

Co se týče učení na zkoušku, tak to hodnotné a těžké jsou: věty o hierarchii (princip je velmi podobný u deterministických, nedeterministická jede přes translační lemma!), borodinovu větu (není zas tak těžká, když použijete lemmata), hierarchie (je tam spoustu vztahů, které se dají snadno odvodit, ale je potřeba tomu rozumět. Nemyslím si, že je potřeba si pamatovat větu, která se skládá z částí 1-10), QBF (skoro jako Savič, materiál v příloze), Ladnerovu větu (idea jednoduchá, je potřeba trošku pokroutit závity, aby jste se dostali do dostatečné úrovně negací :-), materiál v příloze). Navíc by to chtělo rozumět alternujícím kvantifikátorům; tady nemám všelék, mě osobně se osvědčilo si to hezky napsat a třídy $\exists C$ si psát do rámečků :-)

V příloze je malý arch se zněním vět, které jsou potřeba na zápočet (snad to jsou všechny). A pár dalších materiálů, ze kterých jsme se učili ty pokročilejší věci (není moje dílo, ale raději ho uploaduju, aby bylo na věky).

Attachments:

• vety-k-zapoctu.pdf

• vety-k-zapoctu.tex

• TQBF-complete.pdf

• ladner.pdf

• ph.pdf

Otázky o5 klasické:
Hlavní: Immerman.
Slyšel jsem: všemožné hierarchie, Borodin, Ladner.

Doplňující:
Příklad PSPACE-úplného problém.
Co by se stalo kdyby byl PSPACE-úplný problém v Pi_k
Jak zní Boromirova věta ;-)

Poznámka: Existuje triviální PSPACE-úplný problém - ať se nemusíte brblat s QSATem:
Vstup:

1. Program P

2. Vstup programu x

3. Délka paměti kterou má program P k dispozici na spočítání P(x) napsaná v unární soustavě.
   Výstup:
   P(x) nebo "došla paměť".

(Ve stejném stylu existují triviální NP-úplný, a další X-úplné problémy)