Sachverhalt:
A.
Mit Ausschreibung vom 28. August 2019 im Schengener Informationssystem (SIS) ersuchten die deutschen Strafverfolgungsbehörden um Fahndung und Festnahme des türkischen Staatsbürgers A._ zwecks Auslieferung. Sie werfen ihm vor, sich als Kader der Arbeiterpartei Kurdistans (PKK) mitgliedschaftlich an einer Vereinigung im Ausland beteiligt zu haben, deren Zwecke oder deren Tätigkeit darauf gerichtet ist, Mord oder Totschlag zu begehen. Am 1. November 2019 wurde A._ am Flughafen Zürich verhaftet. Am 4. November 2019 erliess das Bundesamt für Justiz (BJ) einen Auslieferungshaftbefehl, nachdem es die Auslieferungshaft zunächst nur provisorisch verfügt hatte.
Deutschland richtete am 8. November 2019 ein Auslieferungsersuchen an die Schweiz, dem das BJ am 3. Januar 2020 stattgab. Dagegen erhob A._ Beschwerde an das Bundesstrafgericht und verlangte gleichzeitig die Entlassung aus der Auslieferungshaft. Mit Entscheid vom 5. Mai 2020 hiess das Bundesstrafgericht die Beschwerde gut und hob den Auslieferungsentscheid vom 3. Januar 2020 auf. Insoweit, als A._ die Einrede des politischen Delikts erhoben hatte, schrieb es das Verfahren als gegenstandslos geworden ab. Schliesslich ordnete es die Haftentlassung an. Zur Begründung hielt es im Wesentlichen fest, es fehle an der beidseitigen Strafbarkeit.
B.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 7. Mai 2020 beantragt das BJ, der Entscheid des Bundesstrafgerichts sei insoweit aufzuheben, als damit die Haftentlassung angeordnet worden sei. Gleichzeitig ersucht es darum, der Beschwerde die aufschiebende Wirkung zu erteilen (Verfahren 1C_228/2020). Mit Verfügung vom 8. Mai 2020 hat das Bundesgericht dieses Gesuch gutgeheissen und die vorläufige Aufrechterhaltung der Inhaftierung des Beschwerdegegners angeordnet.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 15. Mai 2020 beantragt das BJ die Aufhebung des Entscheids des Bundesstrafgerichts in seiner Gesamtheit (Verfahren 1C_261/2020). Seiner Eingabe legt es von ihm während der laufenden Beschwerdefrist eingeholte Stellungnahmen des Nachrichtendienstes des Bundes (NDB), der schweizerischen Botschaft in Ankara und des Ministeriums der Justiz und für Europa von Baden-Württemberg bei.
Das Bundesstrafgericht hält in seiner Stellungnahme an der Begründung im angefochtenen Entscheid fest. Der Beschwerdegegner beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen. Zudem sei das BJ anzuweisen, ihn unverzüglich aus der Auslieferungshaft zu entlassen.

Erwägungen:
1.
Die beiden Beschwerden des BJ richten sich gegen denselben Entscheid des Bundesstrafgerichts. Sie stehen in einem engen sachlichen und prozessualen Zusammenhang. Es rechtfertigt sich deshalb, die Verfahren in sinngemässer Anwendung von <ref-law> (in Verbindung mit <ref-law>) zusammenzufassen und durch ein einziges Urteil zu erledigen (Urteil 2A.48/2006 vom 3. November 2006 E. 1 mit Hinweis; nicht publ. in <ref-ruling>).
2.
2.1. Angefochten ist ein Endentscheid des Bundesstrafgerichts betreffend eine Auslieferung im Rahmen der internationalen Rechtshilfe in Strafsachen. Dagegen steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (Art. 82 lit. a, Art. 86 Abs. 1 lit. b und Art. 90 BGG). Das BJ ist zur Beschwerde legitimiert (Art. 89 Abs. 2 lit. a und d BGG i.V.m. <ref-law> [SR 351.1]).
2.2. Gemäss <ref-law> ist gegen einen Entscheid auf dem Gebiet der internationalen Rechtshilfe in Strafsachen die Beschwerde nur zulässig, wenn er unter anderem eine Auslieferung betrifft und es sich um einen besonders bedeutenden Fall handelt (Abs. 1). Ein besonders bedeutender Fall liegt insbesondere vor, wenn Gründe für die Annahme bestehen, dass elementare Verfahrensgrundsätze verletzt worden sind oder das Verfahren im Ausland schwere Mängel aufweist (Abs. 2; <ref-ruling> E. 1 S. 104 ff. mit Hinweisen).
Wie sich aus dem Wort "insbesondere" ergibt, umschreibt <ref-law> die Voraussetzungen eines solchen Falles nicht abschliessend. Ein besonders bedeutender Fall kann auch angenommen werden, wenn sich eine rechtliche Grundsatzfrage stellt; ebenso, wenn die Vorinstanz von der bundesgerichtlichen Rechtsprechung abgewichen ist (<ref-ruling> E. 1.2 S. 22; <ref-ruling> E. 1.2 S. 218; je mit Hinweisen).
Wie sich aus den nachfolgenden Erwägungen ergibt, stellen sich im vorliegenden Auslieferungsfall rechtliche Grundsatzfragen. Insbesondere gilt es zu prüfen, ob es sich bei der PKK bzw. den mit ihr in Zusammenhang stehenden Volksverteidigungskräften (HPG) um eine kriminelle Organisation im Sinne des Schweizer Strafrechts handelt (<ref-law>). Zudem macht das BJ geltend, im Gegensatz zu einem innerstaatlichen Strafverfahren sei im Rahmen eines Rechtshilfeverfahrens die Strafbarkeit lediglich prima facie zu prüfen. In dieser Hinsicht stellt sich die Frage, ob das Bundesstrafgericht einen unzutreffenden Prüfungsmassstab angewendet hat. Die Sachurteilsvoraussetzungen von <ref-law> sind aus diesen Gründen erfüllt.
2.3. Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerden ist einzutreten.
3.
Lehnt das Bundesstrafgericht die Auslieferung ab und hebt es gleichzeitig oder in der Folge auch die Auslieferungshaft auf, ist das BJ grundsätzlich gehalten, seine Zustimmung zur Freilassung des Betroffenen zu erteilen, welche gemäss <ref-law> erforderlich ist. Es kann jedoch nach der bundesgerichtlichen Rechtsprechung bis zum Entscheid des Bundesgerichts über die Anordnung vorsorglicher Massnahmen zuwarten, sofern es spätestens am auf die Zustellung des Haftentlassungsentscheids folgenden Werktag Beschwerde erhebt und als vorsorgliche Massnahme die Aufrechterhaltung der Auslieferungshaft verlangt (Urteil 1C_620/2019 vom 16. Dezember 2019 E. 2 mit Hinweis). Das BJ erhielt den Entscheid des Bundesstrafgerichts am 6. Mai 2020 und erhob tags darauf Beschwerde ans Bundesgericht. Damit durfte es nach der dargelegten Rechtsprechung seine Zustimmung zur Freilassung des Beschwerdegegners vorläufig verweigern.
4.
4.1. Das BJ ist der Auffassung, die bewaffneten und gewaltbereiten Unterorganisationen der PKK - insbesondere die HPG - seien in der vorliegenden Konstellation und im fraglichen Zeitraum auf der Grundlage des deutschen Auslieferungsersuchens als kriminelle Organisation gemäss <ref-law> zu qualifizieren. Eine Verurteilung des Beschwerdegegners sei prima facie wegen entsprechender Unterstützungshandlungen nach Ziff. 1 Abs. 2 dieser Bestimmung auch in der Schweiz möglich. Dabei sei auch zu berücksichtigen, dass Auslieferungen an Deutschland regelmässig ohne Beanstandungen bewilligt würden.
4.2. Nach Massgabe des hier anwendbaren Europäischen Auslieferungsübereinkommens vom 13. Dezember 1957 (SR 0.353.1; im Folgenden: EAUe) sind die Vertragsparteien grundsätzlich verpflichtet, einander Personen auszuliefern, die von den Justizbehörden des ersuchenden Staats wegen einer strafbaren Handlung verfolgt oder zur Vollstreckung einer Strafe oder einer sichernden Massnahme gesucht werden (Art. 1 EAUe). Auszuliefern ist wegen Handlungen, die sowohl nach dem Recht des ersuchenden als auch nach demjenigen des ersuchten Staats mit einer Freiheitsstrafe (oder die Freiheit beschränkenden sichernden Massnahme) im Höchstmass von mindestens einem Jahr oder mit einer schwereren Strafe bedroht sind (Grundsatz der beidseitigen Strafbarkeit, Art. 2 Ziff. 1 EAUe; s.a. <ref-law>).
4.3. Bei der Prüfung der beidseitigen Strafbarkeit befindet der Rechtshilferichter nicht über Schuld und Strafe eines verfolgten Beschuldigten. Es ist nicht seine Aufgabe, abschliessend zu beurteilen, ob eine strafbare Handlung vorliegt und welche spezifischen Straftatbestände erfüllt sind. Diesbezüglich ist grundsätzlich auch kein Beweisverfahren durchzuführen. Der Rechtshilferichter hat lediglich zu prüfen, ob sich gestützt auf das Ersuchen ausreichend konkrete Verdachtsgründe für die im Ausland untersuchte Straftat ergeben. Er ist dabei an die Sachverhaltsdarstellung im Ersuchen gebunden, soweit sie nicht durch offensichtliche Fehler, Lücken oder Widersprüche sofort entkräftet wird (zum Ganzen: <ref-ruling> E. 5.5 S. 190; Urteil 1C_644/2015 vom 23. Februar 2016 E. 3.1, nicht publ. in <ref-ruling>; je mit Hinweisen).
Nach ständiger Praxis nimmt das Bundesgericht bei Ersuchen gestützt auf das EAUe eine sogenannte Prima-facie-Prüfung des objektiven und subjektiven Tatbestands vor. Für die Prüfung der beidseitigen Strafbarkeit nach schweizerischem Strafrecht ist der im Ersuchen dargelegte Sachverhalt so zu subsumieren, wie wenn die Schweiz wegen eines analogen Sachverhalts ein Strafverfahren eingeleitet hätte. Beidseitige Strafbarkeit setzt keine identischen Strafnormen im ersuchenden und ersuchten Staat voraus (zum Ganzen: <ref-ruling> E. 5.5 S. 190 mit Hinweisen).
Keine Rolle spielt bei der Prüfung der beidseitigen Strafbarkeit entgegen dem Vorbringen des BJ, ob Auslieferungen von der Schweiz an den ersuchenden Staat regelmässig ohne Beanstandungen bewilligt werden. Insbesondere ist die Frage, ob Gründe zur Annahme bestehen, dass das ausländische Verfahren rechtsstaatlichen Mindestanforderungen nicht genügt, gestützt auf die im Einzelfall anwendbaren Rechtsnormen jeweils gesondert zu prüfen. Mit der Voraussetzung der beidseitigen Strafbarkeit hat sie nichts zu tun.
4.4.
4.4.1. Gemäss <ref-law> wird mit Zuchthaus bis zu fünf Jahren oder mit Gefängnis bestraft, wer sich an einer Organisation beteiligt, die ihren Aufbau und ihre personelle Zusammensetzung geheim hält und die den Zweck verfolgt, Gewaltverbrechen zu begehen oder sich mit verbrecherischen Mitteln zu bereichern. Ebenso macht sich strafbar, wer eine solche Organisation in ihrer verbrecherischen Tätigkeit unterstützt.
Unter den Begriff der kriminellen Organisation fallen neben den mafiaähnlichen Verbrechersyndikaten auch terroristische Gruppierungen. Nicht dazu gezählt werden hingegen (grundsätzlich) extremistische Parteien, oppositionelle politische Gruppen sowie Organisationen, die mit angemessenen (nicht verbrecherischen) Mitteln um die politische Macht in ihrem Heimatland ringen oder einen Freiheitskampf gegen diktatorische Regime führen (<ref-ruling> E. 4.1 S. 474; <ref-ruling> E. 5.4 S. 188 f.; je mit Hinweisen).
Als Beteiligte im Sinne von <ref-law> sind alle Personen anzusehen, welche funktionell in die kriminelle Organisation eingegliedert sind und im Hinblick auf deren verbrecherische Zweckverfolgung Aktivitäten entfalten. Diese Aktivitäten brauchen (für sich allein) nicht notwendigerweise illegal bzw. konkrete Straftaten zu sein. Es genügen namentlich auch logistische Vorkehren, die dem Organisationszweck unmittelbar dienen (wie z.B. Auskundschaften, Planen oder Bereitstellen der operativen Mittel, insbesondere Beschaffen von Fahrzeugen, Waffen, Kommunikationsmitteln oder Finanzdienstleistungen usw.). Die Beteiligung setzt auch keine massgebliche Funktion innerhalb der Organisation voraus. Sie kann informeller Natur sein oder auch geheimgehalten werden (<ref-ruling> E. 5.4.1 S. 189 mit Hinweis).
Bei Personen, die nicht in die Organisationsstruktur integriert sind, kommt die Tatvariante der Unterstützung in Frage. Diese verlangt einen bewussten Beitrag zur Förderung der verbrecherischen Aktivitäten der kriminellen Organisation. Im Gegensatz zur Gehilfenschaft zu spezifischen Straftaten (<ref-law>) ist für die Unterstützung nach <ref-law> der Nachweis von kausalen Tatbeiträgen im Hinblick auf ein konkretes Delikt nicht erforderlich. So können namentlich das blosse Liefern von Waffen an eine terroristische oder mafiaähnliche Organisation, das Verwalten von Vermögenswerten oder andere logistische Hilfeleistungen von Aussenstehenden unter den objektiven Tatbestand von <ref-law> fallen. Dementsprechend besteht zwischen der Beihilfe zu konkreten Straftaten und dem Organisationstatbestand grundsätzlich echte Konkurrenz. Der subjektive Tatbestand von <ref-law> verlangt jedoch, dass der Unterstützende weiss oder zumindest in Kauf nimmt, dass sein Beitrag der verbrecherischen Zweckverfolgung der kriminellen Organisation dienen könnte. Blosse Sympathisanten oder "Bewunderer" von terroristischen oder mafiaähnlichen Vereinigungen fallen demgegenüber nicht unter den Organisationstatbestand (<ref-ruling> E. 5.4.2 S. 189 mit Hinweis).
4.4.2. Am 12. Dezember 2014 hat der schweizerische Gesetzgeber das Bundesgesetz über das Verbot der Gruppierungen "Al-Qaïda" und "Islamischer Staat" sowie verwandter Organisationen erlassen (SR 122). Er hat jedoch im Übrigen davon abgesehen, eine Liste terroristischer Organisationen aufzusetzen, wie dies andere Länder und internationale Organisationen teilweise getan haben (vgl. dazu die Botschaft vom 14. September 2018 zur Genehmigung und zur Umsetzung des Übereinkommens des Europarats zur Verhütung des Terrorismus mit dem dazugehörigen Zusatzprotokoll sowie zur Verstärkung des strafrechtlichen Instrumentariums gegen Terrorismus und organisierte Kriminalität, BBl 2018 6477 ff. Ziff. 4.1.2.6). Eine derartige förmliche Qualifizierung durch einen anderen Staat oder eine internationale Organisation bildet deshalb weder eine erforderliche noch eine hinreichende Voraussetzung für die Anwendbarkeit von <ref-law> (<ref-ruling> E. 5.9 S. 192 mit Hinweisen). Massgebend ist die Auslegung der in dieser Strafbestimmung enthaltenen generell-abstrakten Definition der "kriminellen Organisation" im Einzelfall, die der Rechtsprechung obliegt (<ref-ruling> E. 4.7 S. 181 f. mit Hinweisen; zur gesetzlichen Entstehungsgeschichte und zu Reformbestrebungen siehe <ref-ruling> E. 4.7.1 f. S. 481 ff. mit Hinweisen). Anhaltspunkte für die Anwendbarkeit dieser Bestimmung auf terroristische Gruppierungen ergeben sich aus dem am 1. Oktober 2003 in Kraft getretenen Tatbestand der Finanzierung des Terrorismus gemäss Art. 260quinquies (vgl. Urteil 1A.181/2006 vom 23. Januar 2007 E. 3.4 mit Hinweisen, nicht publ. in <ref-ruling>). Danach ist Terrorismus als Gewaltverbrechen zu verstehen, mit dem die Bevölkerung eingeschüchtert oder ein Staat oder eine internationale Organisation zu einem Tun oder Unterlassen genötigt werden soll (Abs. 1; vgl. <ref-ruling> E. 4.1 S. 474). Gemäss den angefügten Strafbarkeitsausschlüssen gilt die Tat indessen nicht als Finanzierung einer terroristischen Straftat, wenn sie auf die Herstellung oder Wiederherstellung demokratischer und rechtsstaatlicher Verhältnisse oder die Ausübung oder Wahrung von Menschenrechten gerichtet ist (Abs. 3); ebensowenig findet Abs. 1 Anwendung, wenn mit der Finanzierung Handlungen unterstützt werden sollen, die nicht im Widerspruch mit den in bewaffneten Konflikten anwendbaren Regeln des Völkerrechts stehen (Abs. 4).
Das Bundesgericht stellt zur Beantwortung der Frage, ob eine Gruppierung als terroristische Organisation einzustufen ist, auf deren Zweck bzw. die dafür eingesetzten Mittel und den politisch-sozialen Kontext ab, in dem sie sich bewegt. Im Zusammenhang mit der Einrede des politischen Delikts hat es hervorgehoben, dass die Terrorismus-Definition stark von weltanschaulich-ideologischen Perspektiven geprägt ist ("one man's terrorist is another man's freedom fighter"). Massive Gewaltanwendungen bis hin zu terroristischen Anschlägen reflektieren in gewissen Fällen auch die Verzweiflung von betroffenen Menschen in rücksichtslos und brutal geführten Bürgerkriegen bzw. regionalen Konflikten mit Zehntausenden von Toten und Millionen von Vertriebenen. Bei bürgerkriegsähnlichen Auseinandersetzungen bezichtigen sich regelmässig beide Seiten eines terroristischen Vorgehens oder schwerster Menschenrechtsverletzungen. Die juristische Differenzierung, wo legitimer Widerstandskampf aufhört und terroristische Kriminalität beginnt, gehört vor diesem Hintergrund zu den delikatesten Aufgaben der internationalen Rechtshilfe (<ref-ruling> E. 4.3 S. 179 f. mit Hinweisen). Ein wesentlicher Gesichtspunkt ist in diesem Zusammenhang, welchen Stellenwert die Anwendung von Gewalt im Vorgehen der betreffenden Gruppierung besitzt und ob bzw. in welchem Mass davon auch Zivilpersonen oder zivile Einrichtungen betroffen sind (vgl. <ref-ruling> E. 4.8 S. 489 f.; <ref-ruling> E. 5.11 S. 194 und nicht publ. E. 3.5.1).
Bei der Abgrenzung zwischen Terrorismus und legitimem Widerstandskampf ist den konkreten Aktivitäten der fraglichen Organisation im Zeitpunkt der verfolgten Straftaten Rechnung zu tragen (<ref-ruling> E. 5 S. 64 mit Hinweis). Diese können sich ebenso wandeln wie der Konfliktskontext und das Verhalten des betroffenen Staats, weshalb Aussagen über den Charakter einer Organisation im Licht von <ref-law> immer zeitgebunden sind.
4.5. Bei Auslieferungsersuchen wegen Terrorismusvorwürfen betreffend Staaten, die von bürgerkriegsähnlichen oder gewalttätigen separatistischen Auseinandersetzungen betroffen sind, hat das BJ im Auslieferungsverfahren ausreichende Sachinformationen (insbesondere zum historischen und völkerrechtlich-humanitären Kontext der fraglichen Konflikte) einzuholen, welche dem Rechtshilferichter die Prüfung erlauben, ob dem Auslieferungsersuchen eine Strafverfolgung wegen Terrorismus zugrunde liegt. Was konkrete Vorwürfe gegen verfolgte Personen in einem stark politisierten Kontext betrifft, stellt das Bundesgericht grundsätzlich auch erhöhte Anforderungen an die Ausführlichkeit und Widerspruchsfreiheit des Ersuchens (Urteil 1C_644/2015 vom 23. Februar 2016 E. 3.2 mit Hinweisen, nicht publ. in <ref-ruling>). Sind die betreffenden Darlegungen des BJ und des ersuchenden Staats nicht ausreichend, ist die Angelegenheit zu weiteren Abklärungen bzw. zur Ergänzung des Rechtshilfeersuchens an das BJ zurückzuweisen, soweit ein solches Vorgehen unter den konkreten Umständen aussichtsreich und angebracht erscheint, andernfalls ist die Auslieferung abzulehnen (vgl. <ref-ruling> E. 7 S. 76; Urteil 1C_91/2007 vom 23. Oktober 2007 E. 2.5.1).
5.
5.1. Gemäss dem Haftbefehl des Oberlandesgerichts Stuttgart vom 25. Juli 2019, welcher dem Auslieferungsersuchen beiliegt, wird der Beschwerdegegner verdächtigt, sich spätestens ab Juni 2014 als (Voll-) Kader der PKK mitgliedschaftlich an einer Vereinigung im Ausland beteiligt zu haben, deren Zwecke oder deren Tätigkeit darauf gerichtet sind, Mord oder Totschlag zu begehen. Zunächst habe er sich bis September 2014 als Führungsfunktionär des PKK-Jugenddachverbandes Ciwanên Azad im Raum Stuttgart beteiligt. Dieser Verband sei in Deutschland und Europa massgeblich mit der Rekrutierung jugendlicher Anhänger für die PKK bzw. für den von dieser Vereinigung geführten bewaffneten Kampf befasst. Ab August 2015 bis März 2016 habe er sich, im Anschluss an Einsätze als PKK-Kader in Belgien und in Frankreich, als verantwortlicher Leiter des PKK-Gebiets Saarbrücken/Saarland betätigt.
Bei der PKK handelt es sich dem Ersuchen zufolge um eine 1978 in der Türkei gegründete Vereinigung, die ihren strukturellen Schwerpunkt in den von Kurden besiedelten Gebieten in der Türkei und den angrenzenden Regionen in Syrien, im Irak und im Iran hat. Sie verfüge über bewaffnete (Guerilla-) Kampfeinheiten (HPG), die ausdrücklich ein Recht zur "aktiven Verteidigung" und zu "Vergeltungsangriffen" gegen türkische Sicherheitskräfte in Anspruch nähmen. Hierzu verübten sie unter anderem Anschläge mit Sprengstoff und Schusswaffen, bei denen häufig Soldaten und Polizisten, zuweilen aber auch Zivilisten, verletzt und getötet würden. Zu den wesentlichen Aufgaben der in Deutschland tätigen PKK-Führungsfunktionäre gehörten die Beschaffung von Finanzmitteln, die Planung, Vorbereitung und Durchführung von öffentlichkeitswirksamen Aktionen bzw. Veranstaltungen zur Beeinflussung der öffentlichen Meinung im Sinne der PKK sowie die Rekrutierung von Nachwuchs für die Guerilla und den Kaderapparat.
Zu den einzelnen Tatbeiträgen des Beschwerdegegners wird konkret ausgeführt, dieser sei als verantwortlicher Kader des Verbands Ciwanên Azad ab Juni 2014 bis September 2014 in Stuttgart mit der Initiierung, Vorbereitung und Durchführung propagandistischer PKK-Veranstaltungen befasst gewesen. Dabei sei er selber häufig als indoktrinierender Redner aufgetreten. Im Haftbefehl werden diesbezüglich verschiedene Aktionen aufgeführt, an denen der Beschwerdegegner in massgeblicher Weise beteiligt gewesen sei. In der Folge seien sechs junge Männer aus dem Raum Stuttgart in die Türkei ausgereist, um von dort zu den Kampfgebieten in Syrien zu gelangen. Der Beschwerdegegner sei bestrebt gewesen, Interessierte zu veranlassen, in die von der PKK beherrschten Gebiete zu reisen, um dort in Ausbildungslagern an Schulungen für Kampfeinsätze teilzunehmen. Dies habe zumindest bei B._ und C._ insofern zum Erfolg geführt, als sich diese beiden, den Aufrufen des Beschwerdegegners Folge leistend, in das nahöstliche Kampfgebiet der PKK begeben hätten. C._ habe dort (mutmasslich in Syrien und/oder im Irak) unmittelbaren Kontakt zu Kämpfern und hochrangigen Funktionären bzw. Kommandeuren der HPG gefunden. B._ sei im April 2016, begleitet von weiteren PKK-Aktivisten, in den Irak gereist, um von dort nahegelegene Gefechtsräume der HPG aufzusuchen, nachdem er sich offenbar bereits im Jahr 2014 am Kampf gegen den IS in Syrien beteiligt gehabt habe. In der Folge habe er bei Operationen der PKK-Guerilla im Nordirak den Tod gefunden.
Als verantwortlicher Leiter des PKK-Gebiets Saarbrücken/Saarland sei der Beschwerdegegner allgemein für sämtliche organisatorischen, finanziellen, personellen und propagandistischen Angelegenheiten der PKK in seinem Zuständigkeitsbereich und für die Koordinierung der damit verknüpften Tätigkeiten verantwortlich gewesen. Dabei sei er insbesondere mit der Vorbereitung, Durchführung und Abwicklung propagandistischer Veranstaltungen sowie Rekrutierungsmassnahmen befasst gewesen. Auch diesbezüglich werden im Haftbefehl eine Reihe von konkreten Veranstaltungen genannt, an welchen der Beschwerdegegner als Redner bzw. als koordinierender Organisator eingebunden gewesen sei.
5.2. Während das BJ in seinem Auslieferungsentscheid gestützt auf die Angaben im Auslieferungsersuchen davon ausging, das beschriebene Verhalten würde in der Schweiz unter den Tatbestand der Unterstützung einer kriminellen Organisation fallen, hält das Bundesstrafgericht im angefochtenen Entscheid fest, es sei zweierlei zu prüfen: erstens die mitgliedschaftliche Beteiligung an der PKK und zweitens die Unterstützung der HPG.
In Bezug auf die erste Variante (Beteiligung) erwägt das Bundesstrafgericht, es sei zu untersuchen, ob die PKK als kriminelle Organisation qualifiziert werden könne. Es legt ausführlich Entstehungsgeschichte, Zweck und Struktur der PKK sowie das Verhalten der Schweizer Behörden ihr gegenüber dar. Zusammenfassend hält es fest, das ursprüngliche Ziel der PKK sei gewesen, in den von Kurden besiedelten Gebieten im Osten der Türkei und den angrenzenden kurdischen Regionen in Syrien, Iran und Irak einen sozialistischen kurdischen Nationalstaat unter ihrer alleinigen Führung zu gründen. Die Gründung der PKK sei als Reaktion auf die Unterdrückung der kurdischen Identität durch den türkischen Staat erfolgt. Ab 1984 habe sie gewaltsam für einen unabhängigen Kurdenstaat und später, nach Aufgabe dieses Ziels, für die kulturellen Rechte der Kurden gekämpft. Die Frage der kulturellen und politischen Rechte der Kurden in der Türkei sei auch heute, nach dem inzwischen gescheiterten Friedensprozess, von zentraler Bedeutung. Diese Zielsetzungen liessen die PKK nicht als eine Organisation erscheinen, deren Zweck es in erster Linie bzw. in überwiegendem Masse sei, Gewaltverbrechen zu begehen. Die PKK werde durch die ihr zugeordneten Unterorganisationen zwar immer wieder in Verbindung auch mit Gewaltverbrechen gebracht, aber ihre Zielsetzungen liessen sie eher als (extremistische) politische Partei oder als Widerstands- und Unabhängigkeitsbewegung denn als kriminelle Organisation im Sinne von <ref-law> erscheinen. Dabei sei zu beachten, dass von der PKK verfolgte Anliegen auch bei hiesigen Behörden grundsätzlich auf Verständnis stiessen. Dies gelte im vorliegenden Fall umso mehr, als die PKK gerade im Zeitraum der unterstellten Beteiligung des Beschwerdegegners in der Türkei eine der am dortigen Friedensprozess beteiligten Parteien gewesen sei. Damit bestehe eine wesentliche Parallele zur Bewegung der LTTE ("Liberation Tiger of Tamil Eelam"), die Gegenstand des <ref-ruling> bildete (a.a.O., E. 4.7.4 S. 488). Eine weitere Parallele zur Bewegung der LTTE liege auch in den die Aktivitäten der PKK einschränkenden Massnahmen im Jahre 2008. So seien Geldsammlungen allein deswegen verboten worden, um eine Eskalation der Gewaltausübung in der Schweiz anlässlich von Sammelaktionen zu verhindern, nicht um damit den Terrorismus zu bekämpfen. Auch die Behandlung der PKK durch die schweizerischen Behörden unterscheide sich damit deutlich von derjenigen, welche einer kriminellen Organisation im Sinne von <ref-law> zukommen würde.
Hinsichtlich der zweiten Variante (Unterstützung) verweist das Bundesstrafgericht zunächst auf einen Entscheid aus dem Jahr 2012, in dem es die HPG als kriminelle Organisation einstufte (TPF 2012 114). Anhand der Ausführungen im Auslieferungsersuchen werde allerdings ersichtlich, dass der Beschwerdegegner nicht wie der von jenem Entscheid Betroffene Kämpfer für den Kampf gegen den türkischen Staat in der Türkei, sondern offensichtlich für den Kampf der Kurden gegen den IS in Syrien und im Irak rekrutiert haben solle. Eine Rekrutierung von Kämpfern für den Kampf gegen den türkischen Staat wäre im hier interessierenden Zeitraum (Juni bis September 2014) zudem wenig wahrscheinlich, da sich die PKK damals am türkischen Friedensprozess beteiligt habe. Die PKK bzw. die HPG als ihr bewaffneter Arm habe im Jahr 2014, dem Aufruf der kurdischen Miliz YPG zu einer Generalmobilmachung für die Verteidigung Rojavas folgend, Kämpfer rekrutiert, welche die YPG im Kampf gegen die Angriffe des IS auf die von Kurden besiedelten Gebiete in Syrien, aber auch im Irak, unterstützten. Die Rekrutierung sei somit zu Gunsten einer Bürgerkriegspartei im Rahmen einer militärischen Auseinandersetzung erfolgt. Der hauptsächliche Zweck habe darin bestanden, die kurdische Zivilbevölkerung in Syrien bzw. im Irak gegen die Angriffe des IS zu beschützen und sie damit vor Vertreibung, Entführungen, Vergewaltigung, Versklavung, Hinrichtungen und Unterdrückung zu bewahren. Vor diesem Hintergrund sei nicht erkennbar, inwiefern die militärischen Aktivitäten der YPG in Syrien bzw. im Irak bzw. deren Unterstützung durch die HPG hauptsächlich auf die Verübung von Gewaltverbrechen ausgerichtet gewesen wären, wie dies für die Qualifikation der YPG als kriminelle Organisation im Sinne von <ref-law> notwendig wäre. Deshalb könnten die dem Beschwerdegegner im Rahmen des Auslieferungsersuchens konkret zur Last gelegten Handlungen bezüglich der Rekrutierung von Kämpfern im Jahr 2014 nicht unter den Tatbestand der Unterstützung einer kriminellen Organisation im Sinne von <ref-law> subsumiert werden. Bezüglich seiner Funktion als verantwortlicher Leiter des PKK-Gebiets Saarbrücken/Saarland (August 2015 bis März 2016) blieben die Ausführungen zu seiner Rekrutierungstätigkeit im Rahmen des Auslieferungsersuchens sehr vage. Es werde lediglich eine Nachricht des Beschwerdegegners wiedergegeben, wonach es einen "Arbeiter" gebe, den er "neu eingestellt" habe. Welche Aufgabe dieser rekrutierten Person zugekommen sein solle, lasse sich dem Ersuchen nicht entnehmen, womit auch diesbezüglich keine Hinweise vorlägen, die eine Subsumtion des Verhaltens des Beschwerdegegners unter den Tatbestand der Unterstützung einer kriminellen Organisation zulassen würden.
5.3. Das BJ ist dagegen der Auffassung, die bewaffneten und gewaltbereiten Unterorganisationen der PKK - insbesondere die HPG - seien auch in der vorliegenden Konstellation und im fraglichen Zeitraum auf der Grundlage des deutschen Auslieferungsersuchens als kriminelle Organisation gemäss <ref-law> zu qualifizieren und eine Verurteilung des Beschwerdegegners wäre prima facie wegen entsprechender Unterstützungshandlungen gemäss <ref-law> auch in der Schweiz möglich. Die PKK sei als einheitlich organisierte Struktur zu verstehen, die grenzüberschreitend tätig sei. Die Zielsetzungen der Organisation und ihre Kommandostrukturen blieben unabhängig davon bestehen, wo und gegen wen ihre bewaffneten Unterorganisationen zum Einsatz kämen.
Das BJ verweist in diesem Zusammenhang auf die von ihm eingeholten Stellungnahmen des NDB vom 12. Mai 2020, der schweizerischen Botschaft in Ankara vom 11. Mai 2020 und des Ministeriums der Justiz und für Europa von Baden-Württemberg vom 13. Mai 2020. Aus der Stellungnahme des NDB ergebe sich namentlich, dass die PKK insbesondere die Rekrutierung und personelle Besetzung der ihr zugehörigen bewaffneten Organisationen (HPG und YPG) letztlich steuere und die HPG/YPG im fraglichen Zeitraum auch in der Türkei mehrere Anschläge verübt hätten. Die schweizerische Botschaft habe auf die Wichtigkeit der Unterscheidung zwischen Kurden und der PKK sowie die totalitären Tendenzen der PKK hingewiesen. So habe sich diese in Nordsyrien mit der Unterdrückung anderer Ethnien oder Mitgliedern anderer Religionen (z. B. Christen) an die Macht gebracht, und zudem habe sie Säuberungen gegenüber Andersdenkenden durchgeführt. Dazu gehörten auch gemässigte Kurden, von denen 400'000 in der Türkei Zuflucht gesucht hätten. Weiter sei die Rede von Rekrutierungen von Kindersoldaten, von willkürlichen Inhaftierungen, Misshandlung von Gefangenen, "Verschwindenlassen" und Morden an Personen, welche die PYD (Schwesterorganisation der PKK in Syrien) ablehnten.
Das Rekrutieren von Kämpfern für den bewaffneten Kampf der PKK in Syrien und im Irak sei damit nicht anders zu beurteilen, als wenn die Kämpfer in der Türkei selbst eingesetzt werden sollten. Nach den erwähnten Berichten des NDB und der schweizerischen Botschaft könne nicht davon ausgegangen werden, dass eine Rekrutierung von Kämpfern für den Einsatz in Nordsyrien im Kampf gegen den IS in der fraglichen Zeitspanne einen Fall von legitimer Anwendung von Gewalt darstelle. Es könne insbesondere nicht gesagt werden, dass die PKK bzw. ihre Unterorganisationen dabei das humanitäre Völkerrecht respektiert hätten. Insgesamt liessen sich die militärischen und terroristischen Tätigkeiten der HPG/YPG nicht trennen.
Diese Umstände würden durch die Ergänzungen des Oberlandesgerichts Stuttgart bestätigt, die das Ministerium der Justiz und für Europa von Baden-Württemberg nachgereicht habe. Die deutschen Behörden führten ebenfalls aus, dass die PKK bzw. deren Guerillakampfverbände während des proklamierten Friedensprozesses ihre Kampfhandlungen nicht vollständig aufgegeben hätten. Auch während der Friedensphase in der Zeit von März 2013 bis Mitte 2015 hätten die (HPG-) Guerillaeinheiten ihre Angriffe danach nicht eingestellt, sondern fortgeführt, wenn auch zeitweise in zahlenmässig reduziertem Umfang. So hätten etwa am 20. August 2014 HPG-Kämpfer mit Raketen und Gewehren im Landkreis Kocaköy (Provinz Diyarbakir) die Gendarmeriekommandantur, das Polizeipräsidium und Dienstwohnungen der Polizei bzw. des Militärs angegriffen. Allein im Zeitraum von Mitte Juli bis Ende Dezember 2015 seien zudem über 700 Einzelakte bekannt, die Verletzte und Tote gefordert hätten. Die HPG seien somit im vorliegend zu beurteilenden Zeitraum entgegen der Darstellung des Bundesstrafgerichts in der Türkei weiterhin aktiv gewesen.
5.4. Der Beschwerdegegner schliesst sich im Wesentlichen den Erwägungen des Bundesstrafgerichts an. Er bringt zudem vor, gemäss dem Auslieferungsersuchen sei B._ im April 2016 in den Nahen Osten gereist. Die Abreise sei damit fast zwei Jahre nach der angeblichen Rekrutierung erfolgt und könne deshalb nicht ihm zugerechnet werden. Weiter weist er darauf hin, dass sich die PKK bereits 1995 gegenüber dem Internationalen Komitee vom Roten Kreuz (IKRK) verpflichtet habe, das humanitäre Völkerrecht zu beachten. Auch das Kassationsgericht Brüssel gehe im Übrigen in einem Urteil vom 28. Januar 2019 davon aus, dass es sich bei der PKK nicht um eine terroristische Organisation handle. Und gemäss einem Entscheid des Gerichts der Europäischen Union vom 15. November 2018 sei die PKK zwischen 2014 und 2017 wegen Verfahrensfehlern zu Unrecht auf der EU-Terrorliste geführt worden. Die neuen Vorbringen des BJ hält der Beschwerdeführer schliesslich für prozessual unzulässig.
5.5. Im angefochtenen Entscheid hat das Bundesstrafgericht den Sachverhalt aus eigenem Antrieb in umfangreicher Weise ergänzt, dies, obwohl es die Sachverhaltsdarstellung im Auslieferungsersuchen zuvor als ausreichend bezeichnet und die dagegen gerichtete Kritik des Beschwerdegegners verworfen hatte. Sinngemäss geht aus der Beschwerdeschrift hervor, dass das BJ die betreffenden vorinstanzlichen Feststellungen in verschiedener Hinsicht als unhaltbar erachtet (<ref-law>). Dies betrifft nach dem Dargelegten insbesondere die Frage anhaltender Anschläge der HPG in der Türkei und ihr Vorgehen in Syrien. Die erst nach dem angefochtenen Entscheid eingeholten Berichte stellen vor diesem Hintergrund neue Beweismittel und die darin enthaltenen Ausführungen neue Tatsachen dar, zu denen erst der Entscheid der Vorinstanz Anlass gegeben hat. Sie sind deshalb im bundesgerichtlichen Verfahren ausnahmsweise zulässig (<ref-law>).
5.6. Indem das Bundesstrafgericht darlegt, es sei zum einen die mitgliedschaftliche Beteiligung an der PKK und zum andern die Unterstützung der HPG zu beurteilen, geht es davon aus, dass es sich dabei im Licht von <ref-law> um zwei unterschiedliche Organisationen handelt. Dies entspricht seiner bisherigen Rechtsprechung (vgl. TPF 2012 114), steht jedoch in einem gewissen Spannungsverhältnis zu seinen eigenen Formulierungen in Bezug auf das Verhältnis zwischen der PKK und den HPG. Danach handelt es sich bei den HPG um den "militärischen Arm" der PKK. Auch in Bezug auf die Rekrutierungstätigkeit unterscheidet das Bundesstrafgericht nicht zwischen den HPG und der PKK. Im erwähnten Entscheid aus dem Jahr 2012 hielt es zudem ausdrücklich fest, eine Zurechnung der damals zur Diskussion stehenden gewaltbereiten Organisationen, d. h. den HPG und den "Freiheitsfalken Kurdistans" (TAK), zur PKK sei genügend erstellt (a.a.O., E. 7.9.5 S. 126). Dies entspricht im Übrigen den Ausführungen im Auslieferungsersuchen, wonach die PKK über die HPG "verfüge", und im Amtsbericht des NDB vom 12. Mai 2020, wonach die HPG zusammen mit anderen Gruppierungen der zentralen Kontrolle der PKK unterstünden. Welche Konsequenzen diese Feststellungen in Bezug auf die Anwendbarkeit von <ref-law> haben und welche Rolle dabei die unterschiedlichen Tätigkeitsfelder der PKK und der HPG spielen, kann vorliegend jedoch offenbleiben, sofern die Auffassung des BJ zutrifft, dass das dem Beschwerdegegner vorgeworfene Verhalten prima facie jedenfalls eine Unterstützung der als kriminelle Organisation einzustufenden HPG in ihrer verbrecherischen Tätigkeit darstellt (vgl. in diesem Zusammenhang auch die Ausführungen zur linksextremen Gruppierung TKP/ML und ihrem militärischen Arm TIKKO in <ref-ruling> E. 5.10-5.12 S. 192 ff.).
5.7. Aus der neueren Rechtsprechung sind für den vorliegenden Fall mehrere Bundesgerichtsurteile von Interesse (s. auch die Hinweise auf ältere Urteile in <ref-ruling> E. 5.3.1 S. 70). In <ref-ruling> und <ref-ruling> hatte das Bundesgericht zwei Fälle von verfolgten kurdischstämmigen Widerstandskämpfern zu beurteilen, die von der Türkei mittels Auslieferungsersuchen verfolgt wurden. Im einen Fall ging es um einen mutmasslichen Helfer der linksextremen separatistischen Organisation DHKP-C, im andern um ein mutmassliches Führungsmitglied der PKK. Eine Auseinandersetzung mit der Frage, ob es sich um kriminelle Organisationen im Sinne des StGB handelte, konnte aus unterschiedlichen Gründen offenbleiben.
Gemäss <ref-ruling> erfüllte die im serbisch-kosovarischen Bürgerkrieg kämpfende "Albanian National Army" (ANA) jedenfalls ab Frühjahr 2003 die Tatbestandsmerkmale einer kriminellen Organisation im Sinne von <ref-law>. Spätestens ab Mitte April 2003 beanspruchte sie, neben Anschlägen gegen serbische Armee- und Polizeikräfte, auch die Urheberschaft eines Bombenanschlags gegen zivile Einrichtungen (die Eisenbahnbrücke in Zvecan). Der Verfolgte hatte die ANA damals von der Schweiz aus logistisch und finanziell unterstützt. Namentlich hatte er sich an der Planung und Koordination von Anschlägen beteiligt und für die ANA finanzielle Mittel beschafft. Über die im Februar 2003 geplante und ausgeführte Tötung eines serbischen Polizisten war er zumindest informiert gewesen. Vor und nach der Aktion hatte er mit den Hauptverdächtigen kommuniziert. Ausserdem hatten sich die Täter nach dem Tötungsdelikt in einem Haus von ihm versteckt. Eine physische Teilnahme an der Tatausführung vor Ort wurde ihm hingegen nicht vorgeworfen (<ref-ruling> E. 2.13 f. S. 242 ff.).
In <ref-ruling> qualifizierte das Bundesgericht die TKP/ML bzw. jedenfalls ihren (organisatorisch integrierten) militärischen Arm TIKKO als kriminelle Organisation. Die TKP/ML (bzw. ihr militärischer Arm TIKKO) hatte über viele Jahre hinweg zahlreiche Anschläge mit Schusswaffen und Sprengstoff verübt und dabei neben Militärpersonen auch Zivilisten getötet. Ausserdem war die Organisation laut Ersuchen für diverse massive gewaltsame Anschläge (auch noch in jüngerer Zeit) gegen zivile Einrichtungen wie Wasserkraftwerke oder Mobilfunkstationen verantwortlich (a.a.O., E. 5.11 S. 194).
<ref-ruling> schliesslich betraf ein schweizerisches Strafverfahren, weshalb die Besonderheiten des Rechtshilferechts (Prima-facie-Massstab und Grundsatz der Verbindlichkeit der Angaben im ausländischen Rechtshilfeersuchen) nicht zum Tragen kamen. Das Bundesgericht erwog, die "Liberation Tigers of Tamil Eelam"-Bewegung (LTTE) gelte zwar als Urheberin diverser terroristischer Anschläge. Sie sei in der Schweiz jedoch nie als terroristische Organisation eingestuft worden und ihr nahe stehende Gruppierungen hätten hier während Jahren Propaganda betreiben und finanzielle Mittel akquirieren können. Für Personen, die zugunsten der Bewegung Gelder und Güter bzw. Hilfsmittel gesammelt hätten, sei unter dem Blickwinkel des Legalitätsprinzips deshalb nicht vorhersehbar gewesen, dass sie sich nach <ref-law> strafbar machen könnten. Wesentlich war in diesem Zusammenhang auch, dass die terroristischen Anschläge neben dem politischen und militärischen Kampf zweitrangig erschienen (E. 4.6 S. 479 ff.).
5.8. Wie das BJ zu Recht hervorhebt, hält der NDB fest, die HPG hätten im hier interessierenden Zeitraum von 2014 bis 2016 mehrere Terroranschläge in der Türkei verübt. Im Einzelnen lässt sich seinem Amtsbericht entnehmen, dass die Terroranschläge in türkischen Städten zu teilweise hohen zivilen Opferzahlen führten, auch wenn die Anschläge jeweils staatlichen Zielen galten. Die PKK versuche zwar grundsätzlich, zivile Opfer zu vermeiden. Nach Abbruch des Annäherungsprozesses zwischen der türkischen Regierung und der PKK Mitte 2015 und vor allem im Verlauf des Jahrs 2016 habe sich die Lage im Krisengebiet in der Südosttürkei aber derart verschlechtert, dass die PKK entgegen ihres eigentlichen Grundsatzes wieder zu Terroranschlägen übergegangen sei und auch einige offen im Namen der HPG verübt habe. Parallel dazu hätten die US-unterstützten YPG erfolgreich den "Islamischen Staat" und andere dschihadistische Gruppierungen in Nordsyrien bekämpft und ihr im syrischen Bürgerkrieg erobertes Autonomiegebiet verteidigt.
Der NDB bestätigt und konkretisiert mit diesen Ausführungen die bereits im Auslieferungsersuchen enthaltene Sachverhaltsdarstellung. Danach war eine Abkehr von der auf die Begehung von Tötungsdelikten fixierten Ausrichtung der PKK zu keinem Zeitpunkt gegeben gewesen. Zudem sei es nach der Proklamation der Selbstverwaltung in verschiedenen von Kurden besiedelten Städten oder Gebieten und der daraufhin staatlicherseits angeordneten Sanktionsmassnahmen zu schweren bewaffneten Auseinandersetzungen zwischen türkischen Militärs bzw. Sicherheitskräften und kurdischen Kämpfern gekommen, in deren weiterem Verlauf HPG-Einheiten eine Vielzahl von Anschlägen verübt hätten, denen zahlreiche türkische Sicherheitskräfte zum Opfer gefallen seien. In ihrer ergänzenden Eingabe listen die deutschen Behörden zudem für die Jahre 2014 bis 2018 beispielhaft Anschläge auf, bei denen auch Zivilpersonen getötet und verletzt und zivile Objekte zerstört wurden.
Gestützt auf die im Rechtshilfeverfahren verbindliche Sachverhaltsdarstellung im Auslieferungsersuchen ist die HPG auch für die Zeit nach dem erwähnten Entscheid des Bundesstrafgerichts aus dem Jahr 2012 prima facie als kriminelle Organisation zu qualifizieren. Ausschlaggebend erscheinen in dieser Hinsicht die anhaltenden Terroranschläge in der Türkei und insbesondere die Tötung von Zivilpersonen sowie die Zerstörung ziviler Objekte (vgl. die in E. 5.7 hiervor wiedergegebene Rechtsprechung). Dass die HPG parallel zu ihren Aktivitäten in der Türkei die YPG im syrischen Bürgerkrieg unterstützte, ändert jedenfalls bei der hier massgeblichen Prima-facie-Beurteilung daran nichts. Dabei kommt es auch nicht darauf an, ob sie in diesem bewaffneten Konflikt das humanitäre Völkerrecht respektierte.
5.9. Hinsichtlich der weiter zu beantwortenden Frage, ob das dem Beschwerdegegner vorgeworfene Verhalten prima facie als Unterstützung einer kriminellen Organisation in ihrer verbrecherischen Tätigkeit angesehen werden kann, stellt das Bundesstrafgericht wie erwähnt in entscheidender Weise darauf ab, dass der Beschwerdegegner offensichtlich Personen für den Kampf der Kurden gegen den IS in Syrien und im Irak rekrutiert haben solle, und verweist in diesem Zusammenhang auf den Umstand, dass in der Türkei zur betreffenden Zeit ein Friedensprozess im Gang war. Dieser Einschätzung ist aus zwei Gründen nicht zu folgen. Zum einen ist nach dem Ausgeführten davon auszugehen, dass die HPG auch während des Friedensprozesses in der Türkei Anschläge verübte. Zum andern erscheint für die Erfüllung des Tatbestands von <ref-law> generell ausreichend, wenn sich rekrutierte Kämpfer in den Dienst einer kriminellen Organisation stellen, und erscheint zweitrangig, in welchem Gebiet sie (zunächst) eingesetzt werden. Dabei ist insbesondere zu berücksichtigen, dass sich die kriminelle Organisation die Kampferfahrung der betreffenden Personen in einem späteren Zeitpunkt auch in anderer Weise zu Nutze machen und den Einsatzort ändern könnte. Das BJ hält deshalb zu Recht fest, es sprenge den Rahmen eines Auslieferungsverfahrens, genau zu untersuchen, auf welchem Gebiet und zu welchem Zweck die rekrutierten Kämpfer eingesetzt würden.
Auch der Einwand des Beschwerdegegners, der im Auslieferungsersuchen erhobene Vorwurf der Rekrutierung von B._ sei aufgrund der erst zwei Jahre später erfolgten Ausreise nicht stichhaltig, überzeugt nicht. Im Ersuchen wird ausgeführt, bereits Anfang November 2014 sei den Ermittlungsbehörden bekannt geworden, dass ein "D._" (Deckname des Beschwerdegegners) nach Syrien gegangen sei, um an der Seite der YPG zu kämpfen, wobei er von einem "B._" begleitet worden sei, der im Kandil-Gebirge noch ausgebildet werden müsse. Die Sachverhaltsdarstellung im Auslieferungsersuchen ist in dieser Hinsicht somit weder widersprüchlich noch lückenhaft. Im Übrigen handelt es sich bei B._ nur um eine von mehreren Personen, mit denen der Beschwerdegegner gemäss Auslieferungsersuchen zum Zweck der Rekrutierung Kontakt aufnahm.
5.10. Zusammenfassend ist somit festzuhalten, dass die Voraussetzung der beidseitigen Strafbarkeit gestützt auf das Auslieferungsersuchen im Rahmen einer Prima-facie-Prüfung bejaht werden kann. Die Kritik des BJ ist begründet, weshalb der angefochtene Entscheid in Bezug auf die Auslieferung aufzuheben ist.
6.
Der angefochtene Entscheid ist darüber hinaus auch hinsichtlich der darin angeordneten Haftentlassung aufzuheben. Im Auslieferungsverfahren ist - anders als bei der strafprozessualen Haft - die Inhaftierung des Verfolgten während des ganzen Verfahrens die Regel, die Entlassung dagegen die Ausnahme (<ref-law>; <ref-ruling> E. 2.2 S. 23 mit Hinweisen). Das Bundesstrafgericht hob die Auslieferungshaft auf, weil es die Auslieferung mangels beidseitiger Strafbarkeit als offensichtlich unzulässig erachtete (Art. 50 Abs. 3 und Art. 51 IRSG). Da dieser Auffassung aus den genannten Erwägungen nicht zu folgen ist, besteht insofern auch kein Grund für eine Haftentlassung. Dass eine solche aus anderen Gründen angezeigt sein könnte, macht der Beschwerdegegner nicht geltend und ist auch nicht ersichtlich. Eine Rückweisung der Sache an das Bundesstrafgericht zur neuen Beurteilung der Zulässigkeit der Haft erübrigt sich somit.
7.
7.1. Der Beschwerdeführer erhob im vorinstanzlichen Verfahren die Einrede, er werde in Deutschland aus politischen Gründen verfolgt. Das Bundesstrafgericht liess diese Frage offen. Grundsätzlich wäre die Sache deshalb zur neuen Beurteilung der Einrede des politischen Delikts an das Bundesstrafgericht zurückzuweisen, worauf bei Vorliegen der gesetzlichen Voraussetzungen (namentlich <ref-law>) erneut die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht zur Verfügung stünde. Aus den im Folgenden darzulegenden Gründen kann hier auf ein solches Vorgehen jedoch ausnahmsweise verzichtet werden.
7.2. Gemäss Art. 3 Ziff. 1 EAUe wird die Auslieferung nicht bewilligt, wenn die strafbare Handlung, derentwegen sie beantragt wird, vom ersuchten Staat als eine politische oder als eine mit einer solchen zusammenhängende strafbare Handlung angesehen wird. Das EAUe definiert den Begriff des politischen Delikts nicht. Art. 3 Ziff. 1 EAUe lässt in dieser Hinsicht Raum für die im ersuchten Staat herrschende Rechtsauffassung (vgl. <ref-ruling> E. 7b S. 409 mit Hinweis; vgl. auch <ref-ruling> E. 3 S. 299 bezüglich eines bilateralen Staatsvertrags) und räumt diesem insofern ein weites Ermessen ein (<ref-ruling> E. 3.4 S. 344; Urteil 1C_559/2011 vom 7. März 2012 E. 3.4, in: SJ 2012 I S. 401). Das Bundesgericht prüft mit freier Kognition, ob ein politisches Delikt vorliegt, das eine Auslieferung ausschliesst (<ref-ruling> E. 3.4 S. 344 mit Hinweisen).
7.3. Gemäss der bundesgerichtlichen Rechtsprechung zu Art. 3 Ziff. 1 EAUe und der entsprechenden innerstaatlichen Bestimmung von <ref-law> ist zwischen sogenannt "absolut" politischen und "relativ" politischen Delikten zu unterscheiden. Absolut politische Delikte stehen in unmittelbarem Zusammenhang mit politischen Vorgängen. Darunter fallen namentlich Straftaten, welche sich ausschliesslich gegen die soziale und politische Staatsorganisation richten, wie etwa Angriffe gegen die verfassungsmässige Ordnung, Landes- oder Hochverrat. Ein relativ politisches Delikt liegt nach der Rechtsprechung vor, wenn einer gemeinrechtlichen Straftat im konkreten Fall ein vorwiegend politischer Charakter zukommt. Der vorwiegend politische Charakter ergibt sich aus der politischen Natur der Umstände, Beweggründe und Ziele, die den Täter zum Handeln bestimmt haben und die in den Augen des Rechtshilferichters vorherrschend erscheinen. Das Delikt muss stets im Rahmen eines Kampfes um die Macht im Staat begangen worden sein und in einem engen Zusammenhang mit dem Gegenstand dieses Kampfes stehen. Darüber hinaus müssen die fraglichen Rechtsgüterverletzungen in einem angemessenen Verhältnis zu den angestrebten Zielen stehen, und die auf dem Spiel stehenden politischen Interessen müssen wichtig und legitim genug sein, um die Tat zumindest einigermassen verständlich erscheinen zu lassen (zum Ganzen: <ref-ruling> E. 4.8.1 f. S. 182 f. mit Hinweisen).
7.4. Beim Tatbestand der kriminellen Organisation handelt es sich nicht um ein absolut politisches Delikt im genannten Sinn, weshalb die Einrede des Beschwerdegegners unter dem Titel des relativ politischen Delikts zu prüfen ist. Das Bundesgericht trifft in seiner Rechtsprechung in dieser Hinsicht dieselbe Unterscheidung zwischen Terrorismus und legitimem Widerstandskampf, wie sie auch für die Strafbarkeit nach <ref-law> massgebend ist (<ref-ruling> E. 4.9 f. S. 184 ff. mit Hinweisen). Sofern die Organisation, deren Unterstützung der Verfolgte beschuldigt wird, als terroristisch zu qualifizieren ist, kann dementsprechend auch nicht gesagt werden, die fraglichen Rechtsgüterverletzungen stünden in einem angemessenen Verhältnis zu den angestrebten Zielen. Fehlt es an der Verhältnismässigkeit in diesem Sinne, geht die Einrede des politischen Delikts somit ins Leere. Da gemäss den obigen Erwägungen das dem Beschwerdeführer vorgeworfene Verhalten prima facie als Unterstützung einer terroristischen Organisation qualifiziert werden kann, ist die Einrede des politischen Delikts aus diesem Grund abzuweisen.
8.
Die Beschwerden sind somit gutzuheissen und der angefochtene Entscheid ist aufzuheben. Der Auslieferungsentscheid des BJ vom 3. Januar 2020 wird damit bestätigt. Die Angelegenheit ist zur neuen Beurteilung der Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens an das Bundesstrafgericht zurückzuweisen.
Der Beschwerdegegner ersucht um unentgeltliche Prozessführung und Rechtsverbeiständung. Da die gesetzlichen Voraussetzungen erfüllt sind, kann dem Gesuch entsprochen werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Verfahren 1C_228/2020 und 1C_261/2020 werden vereinigt.
2.
Die Beschwerden werden gutgeheissen und der Entscheid des Bundesstrafgerichts vom 5. Mai 2020 wird aufgehoben. Die Angelegenheit wird zur neuen Beurteilung der Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens an das Bundesstrafgericht zurückgewiesen.
3.
Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege wird gutgeheissen.
3.1. Es werden keine Gerichtskosten erhoben.
3.2. Rechtsanwalt Gandi Calan wird zum unentgeltlichen Rechtsbeistand ernannt und für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse mit Fr. 2'500.-- entschädigt.
4.
Dieses Urteil wird den Parteien und dem Bundesstrafgericht, Beschwerdekammer, schriftlich mitgeteilt.
Lausanne, 12. Juni 2020
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Der Gerichtsschreiber: Dold